Fundamenta Informaticae - Volume 41, issue 3

Authors: Baier, Christel | Kwiatkowska, Marta

Article Type: Research Article

Abstract: The classification of properties of concurrent programs into safety and liveness was first proposed by Lamport [22]. Since then several characterizations of hierarchies of properties have been given, see e.g. [3, 20, 9, 21]; this includes syntactic characterizations (in terms classes of formulas of logics such as the linear temporal logic) as well as extensional (as sets of computations in some abstract domain). The latter often admits a topological characterization with respect to the natural topologies of the domain of computations. We introduce a general notion of a linear time model of computation which consists of partial and completed computations …satisfying certain axioms. The model is endowed with a natural topology. We show that the usual topologies on strings, Mazurkiewicz traces and pomsets arise as special cases. We then introduce a hierarchy of properties including safety, liveness, guarantee, response and persistence properties, and show that our definition subsumes the hierarchies of: Alpern & Schneider [3]; Chang, Manna & Pnueli [9]; and Kwiatkowska, Peled & Penczek [21]. Syntactic characterizations of the properties in the hierarchy in terms of temporal logic are also studied. Show more

Keywords: Temporal logic, partial order models, safety, liveness, response and persistence properties, topological characterization

DOI: 10.3233/FI-2000-41301

Citation: Fundamenta Informaticae, vol. 41, no. 3, pp. 259-294, 2000

Authors: Moshkov, Mikhail | Chikalov, Igor

Article Type: Research Article

Abstract: An algorithm is considered which for a given decision table constructs a decision tree with minimal depth. The class of all information systems (finite and infinite) is described for which this algorithm has polynomial time complexity depending on the number of columns (attributes) in decision tables.

DOI: 10.3233/FI-2000-41302

Citation: Fundamenta Informaticae, vol. 41, no. 3, pp. 295-299, 2000

Authors: Moshkov, Mikhail

Article Type: Research Article

Abstract: In the paper, infinite information systems are considered which are used in pattern recognition, discrete optimization, computational geometry. Depth and size of deterministic and nondeterministic decision trees over such information systems are studied. Two classes of infinite information systems are investigated. Systems from these classes are best from the point of view of time complexity and space complexity of deterministic as well as nondeterministic decision trees. In proofs methods of test theory [1] and rough set theory [6, 9] are used.

DOI: 10.3233/FI-2000-41303

Citation: Fundamenta Informaticae, vol. 41, no. 3, pp. 301-311, 2000

Authors: Păun, Gheorghe | Rozenberg, Grzegorz | Salomaa, Arto

Article Type: Research Article

Abstract: A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include …the computing power, normal forms, and basic decision problems. Show more

Keywords: Natural Computing, Membrane Computing, Formal Languages, Decidability

DOI: 10.3233/FI-2000-41304

Citation: Fundamenta Informaticae, vol. 41, no. 3, pp. 313-340, 2000

Authors: Tsiatsoulis, Z. | Cotronis, J.Y.

Article Type: Research Article

Abstract: We outline Ensemble, a design and implementation methodology for composing message passing (MP) applications from program components directed by scripts. We define specification components corresponding to program components and we compose them, directed by the same scripts, obtaining formal specifications of the composed applications. We use the Petri net formalism to express component and application specifications. Petri Net composition is modelled by appropriate coupling of inscriptions on interface input and output arcs to and from a unified environment place. We elaborate on testing and debugging of MP applications based on the synergy of tools for Petri-Net simulations with tools for …monitoring program executions. Show more

Keywords: Message Passing Program Composition, Specification Composition, Reuse, Petri Nets, Error Detection

DOI: 10.3233/FI-2000-41305

Citation: Fundamenta Informaticae, vol. 41, no. 3, pp. 341-366, 2000