Fundamenta Informaticae - Volume 25, issue 2

Authors: De La Higuera, Colin | Daniel-Vatonne, Marie-Catherine

Article Type: Research Article

Abstract: Signatures, as introduced to cope with semantics of programming languages, provide an interesting framework for knowledge representation. They allow structured and recursive properties that attribute representation does not permit, and at the same time seem to be algorithmically treatable. We recall how a generalisation relation on terms can be introduced by means of the classical special symbol Ω, whose meaning is “indeterminate”, and the partial order inductively defined on the terms. This formalism can nevertheless not take into account negation or disjunction. We provide in this paper a generalisation relation on sets of terms to withdraw these restrictions. This relation …has different definitions (syntactical, set-theoretic, and based on a closed world assumption) that are proved to be equivalent for specific classes of signatures. They yield an equivalence relation whose canonical form is studied. We also study the combinatorial and algorithmic issues of the generalisation relation: the following problems are proved to be decidable (on finite data) but generally at least NP-complete: Does set A generalise set B? Are sets A and B equivalent? Is set B the canonical form of set A? Compute the negation of set A.... In the case where one of the sets contains only terms maximal for the generalisation relation, the first three problems are shown to be polynomial. Show more

DOI: 10.3233/FI-1996-25201

Citation: Fundamenta Informaticae, vol. 25, no. 2, pp. 99-121, 1996

Authors: Stephens, R. | Thompson, B.C.

Article Type: Research Article

Abstract: Many examples of computational systems compute over infinite sequences of data called streams. We call such systems stream transformers and the study of their theoretical and practical aspects stream processing. In this paper we present a tool for composing stream transformers within an extremely weak second-order, algebraic account of stream processing that comprises a straightforward method for the implementation, specification and verification of stream processing systems.

DOI: 10.3233/FI-1996-25202

Citation: Fundamenta Informaticae, vol. 25, no. 2, pp. 123-174, 1996

Authors: Mäkinen, Erkki

Article Type: Research Article

Abstract: This note introduces subclasses of even linear languages for which there exist inference algorithms using positive samples only.

Keywords: formal languages, grammatical inference, Szilard language, even linear language, reversible language

DOI: 10.3233/FI-1996-25203

Citation: Fundamenta Informaticae, vol. 25, no. 2, pp. 175-181, 1996

Authors: Penczek, Wojciech

Article Type: Research Article

Abstract: Partial order temporal logics interpreted on trace systems have been shown not to have finitary complete axiomatizations due to the fact that the complexity of their decidability problem is in II1 1 . This paper gives infinitary complete proof systems for several temporal logics on trace systems e.g. Computation Tree Logic with past operators and an essential subset of Interleaving Set Temporal Logic.

DOI: 10.3233/FI-1996-25204

Citation: Fundamenta Informaticae, vol. 25, no. 2, pp. 183-200, 1996

Authors: Moshkov, Mikhail

Article Type: Research Article

Abstract: We study the relationships between the complexity of a task description and the minimal complexity of deterministic and nondeterministic decision trees solving this task. We investigate decision trees assuming a global approach i.e. arbitrary checks from a given check system can be used for constructing decision trees.

DOI: 10.3233/FI-1996-25205

Citation: Fundamenta Informaticae, vol. 25, no. 2, pp. 201-214, 1996