Fundamenta Informaticae - Volume 18, issue 2-4

Authors: Richter, Michael M.

Article Type: Research Article

DOI: 10.3233/FI-1993-182-411

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 233-248, 1993

Authors: Steinby, Magnus

Article Type: Research Article

Abstract: In this paper recognizable and rational subsets of general algebras of finite type are studied. These are natural generalizations of the familiar notions originally defined for monoids, but they also include as special cases recognizable and rational tree languages, for example. Some closure properties of the families of recognizable and rational subsets are studied. The operations considered seem to be intimately connected with the recognizability and rationality properties of subsets, and they can also be defined for subsets of abstract algebras, regardless of the nature of the elements. The last part of the paper is devoted to generalized forms of …Kleene’s theorem and related results. Show more

DOI: 10.3233/FI-1993-182-412

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 249-266, 1993

Authors: Proietti, Maurizio | Pettorossi, Alberto

Article Type: Research Article

Abstract: We study the problem of automating some development techniques for logic programs. These techniques are based on the application of semantics preserving transformation rules which are driven by strategies. We propose an abstract strategy which is parametrized by three mathematical functions called definition-folding , selection , and replacement . Once these three functions are supplied, our abstract strategy becomes a concrete one which can be used during program development for driving the application of the Definition, Folding, Unfolding, and Goal Replacement Rules. We show that the definition-folding function can be determined in an automatic way from the description …of the syntactic properties of the program we wish to derive. We also show through some examples that many program derivation strategies described in the literature, such as the methodology for eliminating unnecessary variables, the tupling strategy, the partial deduction techniques, and the promotion strategy, can be viewed as particular instances of our abstract strategy. Show more

DOI: 10.3233/FI-1993-182-413

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 267-286, 1993

Authors: Korec, Ivan

Article Type: Research Article

Abstract: For almost all binary relations R ⊆ N 2 the addition and multiplication on the set N of nonnegative integers (and hence all arithmetical relations) are first order definable in the structure (N ; ⩽, R ). The defining formulae can be chosen independently on R and the words “for almost all” mean “with probability 1” by a very natural probability measure.

DOI: 10.3233/FI-1993-182-414

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 287-296, 1993

Authors: Perlis, Donald

Article Type: Research Article

Abstract: There have been two major efforts at a synthesis of logic and artificial intelligence, one building on the other. I will review these and argue that yet another addition is needed.

DOI: 10.3233/FI-1993-182-415

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 297-305, 1993

Authors: Van Benthem, Johan

Article Type: Research Article

Abstract: We re-analyze the original algebraic proof of the Goldblatt-Thomason theorem characterizing modally definable frame classes, providing an alternative model-theoretic argument. The analysis also provides a more general perspective on the use of algebraic versus model-theoretic methods in Modal Logic.

DOI: 10.3233/FI-1993-182-416

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 307-317, 1993

Authors: Rebagliato, Jordi | Verdú, Ventura

Article Type: Research Article

Abstract: In this paper we study the algebraization of two Gentzen systems, both of them generating the implication-less fragment of the intuitionistic propositional calculus. We prove that they are algebraizable, the variety of pseudocomplemented distributive lattices being an equivalent algebraic semantics for them, in the sense that their Gentzen deduction and the equational deduction over this variety are interpretable in one another, these interpretations being essentially inverse to one another. As a consequence, the consistent deductive systems that satisfy the properties of Conjunction, Disjunction and Pseudo-Reductio ad Absurdum are described by giving apropriate Gentzen systems for them. All these Gentzen systems …are algebraizable, the subvarieties of the variety of pseudocomplemented distributive lattices being their equivalent algebraic semantics respectively. Finally we give a Gentzen system for the conjunction and disjunction fragment of the classical propositional calculus, prove that the variety of distributive lattices is an equivalent algebraic semantics for it and give a Gentzen system, weaker than the latter, the variety of lattices being an equivalent algebraic semantics for it. Show more

DOI: 10.3233/FI-1993-182-417

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 319-338, 1993

Authors: Volger, Hugo

Article Type: Research Article

Abstract: We have shown earlier that the theories which uniformly admit initial families of models resp. disjoint initial families of models resp. initial models are exactly those which are closed under equalizers resp. equalizers and pullbacks (= connected limits) resp. equalizers and products (= arbitrary limits). In addition, syntactical characterizations had been given. To obtain an analogous result for pullbacks we have to weaken the initiality notions. Weakening the uniqueness of the morphism to a uniqueness up to an isomorphism we arrive at the corresponding quasiinitiality notions. As a new result we shall show that the theories which uniformly admit …disjoint quasiinitial families of models resp. quasiinitial models are exactly those which are closed under pullbacks resp. pullbacks and products (= arbitrary limits). As a tool we use a localized version of initiality which was suggested by J.Adamek. Using our result Hébert recently obtained a syntactical characterization for the case of disjoint quasiinitial families. In the case of quasiinitial families the characterization by means of certain class of limit constructions is still an open problem. Show more

DOI: 10.3233/FI-1993-182-418

Citation: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 339-362, 1993