Fundamenta Informaticae - Volume 61, issue 1

Authors: Bandini, Stefania | Simone, Carla

Article Type: Research Article

Abstract: The main aim of this paper is to present the formal description of the Multilayered Reaction-Diffusion Machine (MRDM, an extension of a previously introduced RDM, Reaction-Diffusion Machine) which can be seen as a generalization of Cellular Automata since it relaxes some constraints on uniformity, locality and closure. The MRDM offers a formal and computational environment where to describe, represent and simulate coordination models which explicitly require spatial features to be considered and integrates different …forms of interaction. The paper is divided into two main parts. In the first one, the formal description of the MRDM is presented. In the second part the MRDM is put in relation with deterministic Turing machines; moreover we show how the MRDM, under determined constraints, collapses on a traditional CA. Show more

Citation: Fundamenta Informaticae, vol. 61, no. 1, pp. 1-17, 2004

Authors: Grigorieff, Serge | Margenstern, Maurice

Article Type: Research Article

Abstract: In this paper, we consider cellular automata on special grids of the hyperbolic plane: the grids are constructed on infinigons, i.e. polygons with infinitely many sides. We show that the truth of arithmetical formulas can be decided in finite time with infinite initial recursive configurations. Next, we define a new kind of cellular automata, endowed with data and more powerful operations which we call register cellular automata. This time, starting from finite configurations, it is possible …to decide the truth of arithmetic formulas in linear time with respect to the size of the formula. Show more

Citation: Fundamenta Informaticae, vol. 61, no. 1, pp. 19-27, 2004

Authors: Kiślak-Malinowska, Aleksandra

Article Type: Research Article

Abstract: Pregroups are introduced by Lambek [8] as a framework for syntactic analysis of Natural Language; they are algebraic models of Compact Bilinear Logic. In the present paper we consider the problem of conjoinability in the calculus of pregroups. We show that two types are conjoinable in a pregroup iff they are equal in a free group. This result is analogous to Pentus' characterization of conjoinability in the Lambek calculus [11].

Citation: Fundamenta Informaticae, vol. 61, no. 1, pp. 29-36, 2004

Authors: Polkowski, Lech

Article Type: Research Article

Abstract: Rough sets carry, intuitively, a 3-valued logical structure related to the three regions into which any rough set x divides the universe., viz., the lower definable set i(x), the upper definable set c(x), and the boundary region c(x)\setminus i(x) witnessing the vagueness of associated knowledge. In spite of this intuition, the currently known way of relating rough sets and 3-valued logics is only via 3-valued Łukasiewicz algebras (Pagliani) that endow spaces of disjoint …representations of rough sets with its structure. Here, we point to a 3-valued rough logic RL of unary predicates in which values of logical formulas are given as intensions over possible worlds that are definable sets in a model of rough set theory (RZF). This logic is closely related to the Łukasiewicz 3-valued logic, i.e., its theorems are theorems of the Łukasiewicz 3-valued logic and theorems of the Łukasiewicz 3-valued logic are in one-to-one correspondence with acceptable formulas of rough logic. The formulas of rough logic have denotations and are evaluated in any universe U in which a structure of RZF has been established. RZF is introduced in this note as a variant of set theory in which elementship is defined via containment, i.e., it acquires a mereological character (for this, see the cited exposition of Lesniewski's ideas). As an application of rough logic RL, decision rules and dependencies in information systems are characterized as acceptable formulas of this logic whereas functional dependencies turn out to be theorems of rough logic RL. Show more

Keywords: rough sets, definable sets, rough elementship, rough set theory, rough logic RL, decision rules, dependency rules

Citation: Fundamenta Informaticae, vol. 61, no. 1, pp. 37-45, 2004

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: A finite-state model of communicating processes is presented alongside with the Muller-Bartky model of asynchronous circuits. The purpose of such presentation is to expose a close similarity of these models, at a level of abstraction much lower than the Muller automaton.

Citation: Fundamenta Informaticae, vol. 61, no. 1, pp. 47-59, 2004

Authors: Rudeanu, Sergiu | Vaida, Dragoş

Article Type: Research Article

Abstract: We undertake an axiomatic study of certain semirings and related structures that occur in operations research and computer science. We focus on the properties A,I,U,G,Z,L that have been used in the algebraic study of path problems in graphs and prove that the only implications linking the above properties are essentially those already known. On the other hand we extend those implications to the framework of left and right variants of A,I,U,G,Z,L, and we also prove two …embedding theorems. Further generalizations refer mainly to semiring-like algebras with a partially defined addition, which is needed in semantics. As suggested by idempotency (I) and absorption (A), we also examine in some detail the connections between semirings and distributive lattices, which yield new systems of axioms for the latter. Show more

Keywords: semiring, optimal path problem, fuzzy modelling, partial additive semantics, process algebra, complete existential theory

Citation: Fundamenta Informaticae, vol. 61, no. 1, pp. 61-85, 2004