Fundamenta Informaticae - Volume 23, issue 1

Authors: Ehrenfeucht, Andrzej | Engelfriet, Joost | Pas, Paulien ten | Rozenberg, Grzegorz

Article Type: Research Article

Abstract: We introduce terminally coded (TC) grammars, which generalize parenthesis grammars in the sense that from each word ω generated by a TC grammar we can recover the unlabeled tree t underlying its derivation tree(s). More precisely, there is a length-preserving homomorphism that maps ω to an encoding of t. Basic properties of TC grammars are established. For backwards deterministic TC grammars we give a shift-reduce precedence parsing method without look-ahead, which implies that TC languages can be recognized in linear time. The class of TC languages contains all parenthesis languages, and is contained in the classes of simple precedence languages …and NTS languages. Show more

DOI: 10.3233/FI-1995-2311

Citation: Fundamenta Informaticae, vol. 23, no. 1, pp. 1-32, 1995

Authors: Ch. Meyer, J.-J. | van der Hoek, W.

Article Type: Research Article

Abstract: In this paper we indicate how default logic can be based on epistemic logic, and particularly how we may employ Halpern & Moses' minimal epistemic states for this purpose. In this way we obtain a simple and natural S5-based logic for default reasoning that appears to be cumulative in the sense of Kraus, Lehmann and Magidor.

DOI: 10.3233/FI-1995-2312

Citation: Fundamenta Informaticae, vol. 23, no. 1, pp. 33-65, 1995

Authors: Gasarch, William I. | Kinber, Efim B. | Pleszkoch, Mark G. | Smith, Carl H. | Zeugmann, Thomas

Article Type: Research Article

Abstract: Most work in the field of inductive inference regards the learning machine to be a passive recipient of data. In a prior paper the passive approach was compared to an active form of learning where the machine is allowed to ask questions. In this paper we continue the study of machines that ask questions by comparing such machines to teams of passive machines. This yields, via work of Pitt and Smith, a comparison of active learning with probabilistic learning. Also considered are query inference machines that learn an approximation of what is desired. The approximation differs from the desired result …in finitely many anomalous places. Show more

DOI: 10.3233/FI-1995-2313

Citation: Fundamenta Informaticae, vol. 23, no. 1, pp. 67-89, 1995

Authors: Stewart, Iain A.

Article Type: Research Article

Abstract: We motivate the study of certain classes of acyclic Petri nets and consider the reachability problem for these classes of Petri nets, providing various NP-completeness results. We also show how the reachability problem for the class of acyclic elementary net systems appears to be harder than it is for the (seemingly comparable) class of 1-bounded acyclic Petri nets.

DOI: 10.3233/FI-1995-2314

Citation: Fundamenta Informaticae, vol. 23, no. 1, pp. 91-100, 1995

Authors: de Kogel, Eric

Article Type: Research Article

Abstract: A proposal is made for a formal framework in which equational provability can be represented and investigated. The basic formalism is an algebra of binary relations on ground terms of a first-order language. Two special-purpose mappings are introduced to deal with the structure of terms. Equational provability is characterized in terms of least fixpoints of some mappings. The use of the relational framework is illustrated by a few examples. It is shown that provability of an equation from a finite set of equations, where all equations are variable-free, is decidable. Then we discuss a method by Reeves ([3]) to deal …with equations in semantic tableaux, that we can now prove to be complete in a very simple way. Finally, we discuss an equational proof format that is naturally induced by the relational formulation and serves as a guideline in finding proofs. The relation between Reeves' rules and the construction of such proofs is made explicit. Show more

DOI: 10.3233/FI-1995-2315

Citation: Fundamenta Informaticae, vol. 23, no. 1, pp. 101-121, 1995

Authors: Cadoli, Marco | Schaerf, Marco

Article Type: Research Article

Abstract: We propose a technique for dealing with the high complexity of reasoning under propositional default logic and circumscription. The technique is based on the notion of approximation: A logical consequence relation is computed by means of sound and progressively “more complete” relations, as well as complete and progressively “more sound” ones. Both sequences generated in this way converge to the original consequence relation and are easier to compute. Moreover they are given a clear semantics based on multivalued logic. With this technique unsoundness and incompleteness are introduced in a controlled way and precisely characterized.

DOI: 10.3233/FI-1995-2316

Citation: Fundamenta Informaticae, vol. 23, no. 1, pp. 123-143, 1995