Fundamenta Informaticae - Volume 8, issue 3-4

Article Type: Other

DOI: 10.3233/FI-1985-83-401

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. i-vi, 1985

Authors: Danko, Wktor

Article Type: Research Article

Abstract: In this paper many-sorted logics of programs are considered (cf. Wand [16] and [3]). The aim is to characterize classes of structures axiomatizable by sets of algorithmic formulas. The results are formulated in terms of operations on classes of structures axiomatizable in the first order logic.

Keywords: logics of programs, axiomatizable classes, algorithmic theories

DOI: 10.3233/FI-1985-83-402

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. 269-283, 1985

Authors: Orlicki, Andrzej

Article Type: Research Article

Abstract: In this paper we investigate some properties of categories of enumerated algebras. In section 1 we prove that in case of the category of enumerated algebras satisfying some fixed set of identities, the forgetful functor into the category of enumerated sets is monadic. Then in sections 2 and 3 some applications of this result are presented. In particular, we show (see Theorem 3.2, section 3) that each finitary monad in the category of denumerable sets has a lifting to a monad in the category of enumerated sets.

Keywords: enumerated type of algebras, enumerated algebra, monad, monadic functor, category of enumerated sets

DOI: 10.3233/FI-1985-83-403

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. 285-307, 1985

Authors: Wasilewska, Anita

Article Type: Research Article

Abstract: We introduce the notion of monadic second order definability (m.s.o definability) of automata, programs and logics and point out some classes of automata (theorem 7), programs (theorem 8) and logics (theorem 9) which are m.s.o definable.

Keywords: m.s.o definability, finite automaton, FC-algorithm, theorem proving system

DOI: 10.3233/FI-1985-83-404

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. 309-320, 1985

Authors: Labella, Anna | Pettorossi, Alberto

Article Type: Research Article

Abstract: Various languages, formalisms and algebraic structures have been recently proposed for denoting parallel computations and communications among processes. As in [LaP 83] we restrict our attention to the CCS [Mil 80] and CSP [Hoa 78] languages. We provide categorical models for their basic constructs and operations. The parallel composition and other kinds of interactions among computing processes will be interpreted as categorical constructions in suitable categories.

Keywords: Categorical models, Parallel Computations, Communicating Systems, CCS and CSP Languages

DOI: 10.3233/FI-1985-83-405

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. 321-357, 1985

Authors: Orłowska, Ewa

Article Type: Research Article

Abstract: The purpose of the present paper is to give a logical framework which provides a uniform description of Pawlak’s information systems of deterministic, nondeterministic, and many-valued information. A language is introduced for representing and retrieving information. Logical aspects of dynamics of information systems are discussed.

Keywords: information system, deterministic information, nondeterministic information, many-valued information, information, query language, predicate logic

DOI: 10.3233/FI-1985-83-406

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. 359-378, 1985

Authors: Wojciechowski, Jerzy

Article Type: Research Article

Abstract: In this paper the notion of regular expression for finite automata on transfinite sequences /TF-automata/ is introduced. The characterization theorem for TF-automata is proved. From this theorem we conclude the decidability of the emptiness problem for TF-automata and the characterization theorem for finite automata on transfinite sequences of bounded lenght.

Keywords: finite automata, transfinite sequences, regular expressions

DOI: 10.3233/FI-1985-83-407

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. 379-396, 1985

Authors: Heinz, Alois Peter | Vossen, Gottfried

Article Type: Research Article

Abstract: The problem of optimizing algebraic queries to relational databases which are formulated with the help of inequality selection, projection, and natural join is addressed: We generalize the well-known tableau formalism to handle this type of queries and provide a quadratic-time optimization procedure. We show how optimized tableaux can be translated back into extended SPJ-expressions, thereby dispensing with the computationally harder cartesian product.

Keywords: relational databases, relational algebra, query optimization, tableaux

DOI: 10.3233/FI-1985-83-408

Citation: Fundamenta Informaticae, vol. 8, no. 3-4, pp. 397-414, 1985