Fundamenta Informaticae - Volume 38, issue 4

Authors: Bono, Viviana | Bugliesi, Michele | Dezani-Ciancaglini, Mariangiola | Liquori, Luigi

Article Type: Research Article

Abstract: We extend the type system for the Lambda Calculus of Objects [16] with a mechanism of width subtyping and a treatment of incomplete objects. The main novelties over previous work are the use of subtype-bounded quantification to capture a new and more direct rendering of MyType polymorphism, and a uniform treatment for other features that were accounted for via different systems in subsequent extensions [7, 6] of [16]. The new system provides for (i) appropriate type specialization of inherited methods, (ii) static detection of errors, (iii) width subtyping compatible with object extension, and (iv) sound typing for partially specified objects.

Keywords: Objects, Type System, Subtyping, Type Soundness

DOI: 10.3233/FI-1999-38401

Citation: Fundamenta Informaticae, vol. 38, no. 4, pp. 325-364, 1999

Authors: Bordihn, Henning | Fernau, Henning | Holzer, Markus

Article Type: Research Article

Abstract: We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.

Keywords: accepting systems, determinism in Lindenmayer systems

DOI: 10.3233/FI-1999-38402

Citation: Fundamenta Informaticae, vol. 38, no. 4, pp. 365-375, 1999

Authors: Corradini, Flavio | D'Ortenzio, Domenicantonio | Inverardi, Paola

Article Type: Research Article

Abstract: In this paper we contrast (the core of) four well-known process algebras specifically enriched for the specification and verification of timed systems. The aim of this comparison is twofold. On one hand it permits to gain confidence on how time and time passing are modelled in the four different timed process algebras. On the other hand, it establishes conditions under which mappings from a calculus to another can be provided which preserve (strong bisimulation-based) behavioural equivalence.

Keywords: Distributed Systems, Specification, Verification, Timed Process Algebras, Timed Bisimulations

DOI: 10.3233/FI-1999-38403

Citation: Fundamenta Informaticae, vol. 38, no. 4, pp. 377-395, 1999

Authors: Păun, Gheorghe | Yu, Sheng

Article Type: Research Article

Abstract: The P systems were recently introduced as distributed parallel computing models of a biochemical type. Multisets of objects are placed in a hierarchical structure of membranes and they evolve according to given rules, which are applied in a synchronous manner: at each step, all objects which can evolve, from all membranes, must evolve. We consider here the case when this restriction is removed. As expected, unsynchronized systems (even using catalysts) are weaker than the synchronized ones, providing that no priority relation among rules is considered. The power of P systems is not diminished when a priority is used and, moreover, …the catalysts can change their states, among two possible states for each catalyst. Show more

Keywords: P systems, Synchronization, Recursively enumerable languages, Matrix grammars

DOI: 10.3233/FI-1999-38404

Citation: Fundamenta Informaticae, vol. 38, no. 4, pp. 397-410, 1999