Fundamenta Informaticae - Volume 15, issue 1

Article Type: Other

DOI: 10.3233/FI-1991-15101

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. i-vi, 1991

Authors: Rauszer, Cecylia M.

Article Type: Research Article

Abstract: In the paper we consider properties of minimal sets of attributes (reducts) which determine an equivalence relation ind(P) . We show that the problem to figure out all reducts of a given set is NP -complete. Subsequently, we present some properties of the set of all attributes which are indispensable to create ind(P) .

DOI: 10.3233/FI-1991-15102

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 1-12, 1991

Authors: Hirshfeld, Joram

Article Type: Research Article

Abstract: We investigate possible ways to extend the notion of determinacy from automata to general concurrent systems (described here mainly as behavior structures).

DOI: 10.3233/FI-1991-15103

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 13-36, 1991

Authors: Habel, Annegret | Kreowski, Hans-Jörg | Plump, Detlef

Article Type: Research Article

Abstract: Jungle evaluation is proposed as a new graph rewriting approach to the evaluation of functional expressions and, in particular, of algebraically specified operations. Jungles – being intuitively forests of coalesced trees with shared substructures – are certain acyclic hypergraphs (or equivalently, bipartite graphs) the nodes and edges of which are labeled with the sorts and operation symbols of a signature. Jungles are manipulated and evaluated by the application of jungle rewrite rules, which generalize equations or, more exactly, term rewrite rules. Indeed, jungle evaluation turns out to be a compromise between term rewriting and graph rewriting displaying some favorable properties: …the inefficiency of term rewriting is partly avoided while the possibility of structural induction is maintained, and a good part of the existing graph grammar theory is applicable so that there is some hope that the rich theory of term rewriting is not lost forever without a substitute. Show more

DOI: 10.3233/FI-1991-15104

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 37-60, 1991

Authors: Vakarelov, Dimiter

Article Type: Research Article

Abstract: One of the main results of the paper is a characterization of certain kind similarity relations in Pawlak knowledge representation systems by means of first order sentences. As an application we obtain a complete finite axiomatization of the corresponding poly modal logic, called in the paper MLSim. It is proved that MLSim possesses finite model property and is decidable.

DOI: 10.3233/FI-1991-15105

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 61-79, 1991

Authors: Rodenburg, P.H.

Article Type: Research Article

Abstract: In a natural formulation, Craig’s interpolation theorem is shown to hold for conditional equational logic.

DOI: 10.3233/FI-1991-15106

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 80-85, 1991

Authors: Mäkinen, Erkki

Article Type: Research Article

Abstract: It is shown that left Szilard languages of context-free grammars are pure context-free languages. This is one of the few exceptions among the numerous negative results concerning the generative capacity of pure languages. Moreover, we characterize pure context-free languages and left Szilard languages of pure context-free grammars as certain homomorphic images.

DOI: 10.3233/FI-1991-15107

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 86-89, 1991

Authors: Hromkovič, Juraj | Inoue, Katsushi | Ito, Akira | Takanami, Itsuo

Article Type: Research Article

Abstract: It is well known that four-way two-dimensional alternating finite automata are more powerful than three-way two-dimensional alternating finite automata, which are more powerful than two-way two-dimensional alternating finite automata. This paper shows that four-way, three-way, and two-way two-dimensional “synchronized” alternating finite automata all have the same power as rectangular array bounded automata.

DOI: 10.3233/FI-1991-15108

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 90-98, 1991

Authors: Intrigila, Benedetto

Article Type: Research Article

Abstract: We say that a closed term M is easy in the λ β η -calculus if for every term N the theory λ β η + { M = N } is consistent. The main result of the paper is to show that, for a certain term P , the term P (ω ω ) is easy, while P ω is not. It follows that the easiness of a given M does not imply either easiness or non-easiness of PM , contradicting an earlier conjecture.

DOI: 10.3233/FI-1991-15109

Citation: Fundamenta Informaticae, vol. 15, no. 1, pp. 99-106, 1991