Fundamenta Informaticae - Volume 38, issue 3

Authors: Janicki, Ryszard | Koutny, Maciej

Article Type: Research Article

Abstract: In the formal treatment of concurrent computing systems, causality and weak causality can be used to provide abstract specifications of the temporal ‘earlier than’ and ‘not later than’ orderings. In this paper we consider relational structures comprising causality and weak causality — called stratified order structures — which can be used to provide a non-sequential semantics of Petri nets with inhibitor arcs. We show that this approach can be extended to nets augmented with priority specifications. In particular, we demonstrate how to derive stratified order structures for such nets by generalising the standard construction of causal partial orders based on …occurrence nets. Show more

DOI: 10.3233/FI-1999-38301

Citation: Fundamenta Informaticae, vol. 38, no. 3, pp. 223-255, 1999

Authors: Kappes, Martin

Article Type: Research Article

Abstract: We study the generative capacity of multi-bracketed contextual rewriting grammars. This model is a generalization of multi-bracketed contextual grammars, which were studied in [Kap98a]. They possess an induced Dyck-structure to control the derivation process and to provide derivation trees. The generative capacity of this class is investigated and compared to Chomsky grammars and to tree adjoining grammars with local constraints. It will be shown that this class of grammars covers the basic natural language constructions such as duplication, multiple agreement and crossed-serial dependencies. Furthermore, two natural variants of the derivation relation, namely top-down and bottom-up derivation modes are examined.

Keywords: Contextual Grammars, Tree Adjoining Grammars, Multi-Bracketed Contextual Grammars

DOI: 10.3233/FI-1999-38302

Citation: Fundamenta Informaticae, vol. 38, no. 3, pp. 257-280, 1999

Authors: Koutras, Costas D. | Koletsos, George | Zachos, Stathis

Article Type: Research Article

Abstract: A family of many-valued modal logics which correspond to possible-worlds models with many-valued accessibility relations, has been recently proposed by M. Fitting [7, 8]. Non-monotonic extensions of these logics are introduced with a fixpoint construction à la McDermott & Doyle and employ sequential belief sets as epistemic states [9]. In this paper we take a logical investigation of many-valued modal non-monotonic reasoning in Fitting's formal framework. We examine the notion of MV-stable sets which emerges as a sequential many-valued analog of Stalnaker-Moore stable sets and prove that several attractive epistemic properties are essentially retained in the many-valued setting, esp. when …focusing on a syntactically simple epistemic fragment of MV-stable sets. We show that MV-stable sets are always closed under S4 consequence and identify three sufficient conditions for capturing axioms of negative introspection. Also, the relation of MV-stable sets to many-valued analogs of classical S5 models and to many-valued extensions of universal models is discussed. Finally, we pay special attention to the subclass of logics built on linear Heyting algebras and show that inside this subclass, the situation is very similar - in many respects - to the machinery devised by W. Marek, G. Schwarz and M. Truszczyński. In particular, the normal fragments of the two important classical ranges of modal non-monotonic logics remain intact: many-valued autoepistemic logic is captured by any non-monotonic logic in K5 – KD45 and many-valued reflexive autoepistemic logic corresponds to KTw5 – Sw5. Show more

Keywords: Non-Monotonic Reasoning, Modal Non-Monotonic Logics, Many-Valued Logics, Knowledge Representation, Epistemic Logics

DOI: 10.3233/FI-1999-38303

Citation: Fundamenta Informaticae, vol. 38, no. 3, pp. 281-324, 1999