Fundamenta Informaticae - Volume 20, issue 1,2,3

Authors: Rasiowa, Helena

Article Type: Other

DOI: 10.3233/FI-1994-201239

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 1-2, 1994

Authors: de Bakker, J.W. | de Vink, E.P.

Article Type: Research Article

Abstract: A comparative semantic study is made of two notions in concurrency, viz. atomicity and action refinement. Parallel composition is modeled by interleaving, and refinement is taken in the version where actions are refined by atomized statements. The bisimulation domain used in the semantic definitions is obtained as solution of a system of domain equations over complete metric spaces. Both operational and denotational models are developed, and their equivalence is established using higher-order techniques and Banach’s fixed point theorem. The operational semantics for refinement is based on transition rules rather than on some form of syntactic substitution.

DOI: 10.3233/FI-1994-201231

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 3-34, 1994

Authors: Doyle, Jon

Article Type: Research Article

Abstract: Logical epistemology unduly sways theories of thinking that formulate problems of nonmonotonic reasoning as issues of nondeductive operations on logically phrased beliefs, because the fundamental concepts underlying such reasoning have little to do with logic or belief. These formulations make the resulting theories inappropriately special and hide the characteristic structures of nonmonotonic reasoning amid many unrelated structures. We present a more direct mathematical development of nonmonotonic reasoning free of extraneous logical and epistemological assumptions, and argue that the insights gained in this way exemplify the benefits obtained by approaching psychology as a subject for mathematical investigation through the discipline of …rational psychology. Show more

DOI: 10.3233/FI-1994-201232

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 35-73, 1994

Authors: Ehrenfeucht, A. | Rozenberg, G.

Article Type: Research Article

Abstract: The notion of a square system is introduced and investigated - it is based on a quaternary relation satisfying certain symmetry conditions. The theory of square systems provides a unifying framework for studying decompositions of systems based on hierarchical families of subsets - hence for tree-like decompositions.

DOI: 10.3233/FI-1994-201233

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 75-111, 1994

Authors: Fitting, Melvin

Article Type: Research Article

Abstract: Kleene’s strong three-valued logic extends naturally to a four-valued logic proposed by Belnap. We introduce a guard connective into Belnap’s logic and consider a few of its properties. Then we show that by using it four-valued analogs of Kleene’s weak three-valued logic, and the asymmetric logic of Lisp are also available. We propose an extension of these ideas to the family of distributive bilattices. Finally we show that for bilinear bilattices the extensions do not produce any new equivalences.

DOI: 10.3233/FI-1994-201234

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 113-131, 1994

Authors: Harju, T. | Rozenberg, G.

Article Type: Research Article

Abstract: A subset X of a 2-structure (a reversible edge-colored directed graph) g is a clan, if X cannot be distinguished by colors from outside of X. We show that if g is primitive, i.e. it has no nontrivial clans, then there exists an edge e or an end vertex x such that when e or x is removed from g, the resulting 2-structure g′ remains primitive. We also present a composition result for the unstable 2-structures, which are those primitive 2-structures where a removal of any edge results in a nonprimitive 2-structure.

DOI: 10.3233/FI-1994-201235

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 133-144, 1994

Authors: Minker, Jack | Ruiz, Carolina

Article Type: Research Article

Abstract: The use of explicit negation enhances the expressive power of logic programs by providing a natural and unambiguous way to assert negated information about the domain being represented. We study the semantics of disjunctive programs that contain both explicit negation and negation-by-default, called extended disjunctive logic programs. General techniques are described for extending model, fixpoint, and proof theoretic characterizations of an arbitrary semantics of normal disjunctive logic programs to cover the class of extended programs. Illustrations of these techniques are given for stable models, disjunctive well-founded and stationary semantics. The declarative complexity of the extended programs, as well as the …algorithmic complexity of the proof procedures and fixpoint operators, are discussed. Show more

DOI: 10.3233/FI-1994-201236

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 145-192, 1994

Authors: Montanari, Ugo | Yankelevich, Daniel

Article Type: Research Article

Abstract: Many approaches have been developed with the aim of capturing the advantages of both process algebras and Petri nets in terms of modularity and structure on one side and faithful description of concurrency on the other. A natural way of merging these different models is to express the semantics of process algebras in terms of Petri nets. In this work we present a modular construction of operational models for CCS via different groups of structural axioms. To express them, we use Equational Type Logic (ETL), a formalism based on conditional axioms on typed algebras. Typed algebras can be used with …profit to present transition systems where both states and transitions have algebraic structure, as opposed to the usual SOS approach where only states have structure. We build an algebra in which different types give different views of the language. In fact, different subalgebras live together in the same structure and are related by axioms. They represent: i) the transition system of CCS; ii) an unfolded version of it; iii) a net for CCS and its marking graph; and iv) a folded version of the latter with the same states as i). The model is completely compositional, since CCS operations are defined on all state representations. We also present axioms which directly establish the relation between interleaving and truly concurrent semantics for CCS. Finally, some related work is discussed and the relation of our models with two previous proposals is shown in detail. Show more

DOI: 10.3233/FI-1994-201237

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 193-229, 1994

Authors: Trakhtenbrot, B.A.

Article Type: Research Article

DOI: 10.3233/FI-1994-201238

Citation: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 231-275, 1994