Fundamenta Informaticae - Volume 40, issue 2-3

Authors: Janicki, Ryszard

Article Type: Other

DOI: 10.3233/FI-1999-402309

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. i-ii, 1999

Authors: Koutny, Maciej

Article Type: Research Article

DOI: 10.3233/FI-1999-402301

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 103-107, 1999

Authors: Arnold, André | Point, Gérald | Griffault, Alain | Rauzy, Antoine

Article Type: Research Article

Abstract: The AltaRica formalism is designed for describing complex systems consisting of a number of interacting components. Its semantics is expressed in terms of transition systems so that a system described in this language can be analysed by any technique or tool applicable to transition systems. The components of a system have two kinds of interactions • event synchronisation, like in the synchronized product of transition systems of Arnold and Nivat, • interface coordination: with each component are associated interfaces whose values depend on the state of the component as well as on the values of interfaces of other components of …the system. Another feature of AltaRica is the possibility of defining hierarchical systems: some subsystems can be encapsulated and their mutual interactions as well as their interactions with the rest of the system are supervised by a controller. Show more

Keywords: AltaRica, safety critical systems, transition systems, hierarchical systems, synchronization, interface coordination

DOI: 10.3233/FI-1999-402302

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 109-124, 1999

Authors: Best, Eike | Lavrov, Alexander

Article Type: Research Article

Abstract: We propose generic schemes for basic composition operations (sequential composition, choice, iteration, and refinement) for high-level Petri nets. They tolerate liberal combinations of place types (equal, disjoint, intersecting) and, owing to a parameterised scheme of type construction, allow for weak and strong versions of compositions. Properties such as associativity, commutativity, and coherence with respect to unfolding, are preserved.

Keywords: High-level Petri nets, Composition operators, Process algebras

DOI: 10.3233/FI-1999-402303

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 125-163, 1999

Authors: Busi, Nadia | Pinna, G. Michele

Article Type: Research Article

Abstract: In this paper we introduce a truly concurrent semantics for P/T nets with inhibitor and read arcs, called henceforth Contextual P/T nets. The semantics is based on a proper extension of the notion of process to cope with read and inhibitor arcs: we show that most of the properties enjoined by the classical process semantics for P/T nets continue to hold and we substantiate the adequateness of our notion by comparing it with the step semantics.

Keywords: Contextual Nets, Step Semantics, Process Semantics

DOI: 10.3233/FI-1999-402304

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 165-197, 1999

Authors: Devillers, Raymond | Goossens, Joël

Article Type: Research Article

Abstract: In this paper we study the problem of scheduling hard real-time periodic task sets with a dynamic and preemptive scheduler. We will focus on the response time notion, its interest and its effective computation for the deadline driven scheduler. We present a general calculation procedure for determining the response time of the kth request of a task in asynchronous systems with general as well as arbitrary deadlines. Finally, we analyze the performance of the computation so defined, both in terms of time and memory requirements.

Keywords: hard real-time scheduling, periodic task set, synchronous systems, asynchronous systems, deadline driven scheduler, response time

DOI: 10.3233/FI-1999-402305

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 199-219, 1999

Authors: Maggiolo-Schettini, Andrea | Tini, Simone

Article Type: Research Article

Abstract: In synchronous programming, programs can be perceived as purely sequential, and parallelism is only a logical concept useful to develop programs in a modular way. Classical semantics for synchronous languages interpret programs as sequential input/output finite state machines (i/o FSMs) where concurrency disappears. We argue that semantics where concurrency is reflected can be useful at least for improving hardware implementation, verification, and design of model-based schedulers. So, these semantics should not “compete” with the classical ones but should offer different, although consistent, views of programs, each supporting a particular task in their development. In order to define semantics reflecting concurrency, …well established techniques adopted to define “truly concurrent” semantics for asynchronous languages could be applied. In this paper, we consider as a prototype of the class of synchronous languages the language Esterel, which is gaining use in a wide variety of applications. Then, following a method proposed by Degano and Priami to give semantics for asynchronous process algebras, we develop a semantic framework in which one can define different, although consistent, semantics of Esterel programs. The idea is to define a very concrete model of the language from which more abstract models can be recovered by means of suitable abstraction functions. We define a proved transition system (PTS) as the most concrete model of Esterel. We show that the classical interpretation in FSMs can be recovered from the PTS by a suitable abstraction function, namely we show that our most concrete semantics is consistent with the classical one. Then, from proved trees obtained by unfolding parts of the PTS, we abstract locality trees and enabling trees. We show how locality trees can be used to improve the hardware implementation of the language, namely to remove redundant latches generated by the compiler. Finally, we show how enabling trees can be used to improve the verification phase, namely to isolate program parts which actually cause the violation of a certain property. Show more

Keywords: concurrency, synchronous languages, hardware implementation, observer monitoring

DOI: 10.3233/FI-1999-402306

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 221-250, 1999

Authors: Pietkiewicz-Koutny, Marta

Article Type: Research Article

Abstract: We investigate the synthesis problem for the Elementary Net Systems with Inhibitor Arcs (ENI-systems) executed according to the a-priori semantics. We characterise transition systems generated by ENI-systems, called TSENI transition systems, by adapting the notion of a step transition system whose arcs are labelled by sets of concurrently executed events. The relationship between the ENI-systems and TSENI transition systems is established via the notion of a region. We define, and show consistency of, two behaviour preserving translations between nets and transition systems. We also discuss how to optimise the synthesis procedure by using only minimal regions and selected inhibitor arcs.

Keywords: concurrency, synthesis of Petri nets, theory of regions, morphisms

DOI: 10.3233/FI-1999-402307

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 251-283, 1999

Authors: Shields, M.W.

Article Type: Research Article

Abstract: In this paper, we consider two formal semantics for path programs. The first is a version of the net semantics introduced in [8] and further described in [7], and the second is an extension of the vector semantics of [15]. The extension involves the idea of tagging vectors with sets of sets of action names as with acceptance sets [3, 5] or refusal sets [1, 6] as used in the semantics of certain process algebras. The net semantics of [8, 7] associates a path program with an isomorphism class of labelled, marked nets - two such nets being isomorphic if …they have identical pictorial representations and consequently describe the same system. A behaviour of such a class is an isomorphism class of cycle-free labeled nets showing the (partial) order in which conditions have held and events have occurred. We review these basic ideas and then present a version of the [7] semantics. We next present an acceptance vector semantics for path programs. An acceptance vector consists of a collection of sequences, one for each component path, describing the sequence of actions associated with the path in question during some period of activity, together with a set of actions which are available to continue the behaviour represented by the collection. Finally, we show that the two semantics are related in the sense that every net based behaviour may be transformed into an accceptance vector. Show more

Keywords: Path Expressions, Petri Nets, Concurrency, Vector Languages, Acceptance Sets

DOI: 10.3233/FI-1999-402308

Citation: Fundamenta Informaticae, vol. 40, no. 2-3, pp. 285-316, 1999