Fundamenta Informaticae - Volume 80, issue 1-3

Authors: Kleijn, Jetty | Koutny, Maciej

Article Type: Research Article

Abstract: We are concerned with causality semantics in the executions of Petri nets with range arcs. Range arcs combine (and subsume) the distinctive features of inhibitor and activator arcs, and each such arc provides a means of specifying a range (a finite or infinite interval of non-negative integers) for the number of tokens in a place which makes enabling of a given transition possible. We demonstrate that the existing treatment of causality developed for Petri nets with …inhibitor arcs based on structures generalising partial orders can also be applied to nets with range arcs. Show more

Keywords: theory of concurrency, Petri nets, weighted activator and inhibitor arcs, range arcs, causality semantics, infinite processes, occurrence nets, step sequences

Citation: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 199-219, 2007

Authors: Chalopin, Jérémie | Métivier, Yves

Article Type: Research Article

Abstract: We study the election and the naming problems in the asynchronous message passing model. We present a necessary condition based on Angluin's lifting lemma [1] that must be satisfied by any network that admits a naming (or an election) algorithm. We then show that this necessary condition is also sufficient: we present an election and naming algorithm based on Mazurkiewicz's algorithm [17]. The algorithmwe obtained is totally asynchronous and it needs a polynomial number of messages …of polynomial size, whereas previous election algorithms in this model are pseudosynchronous and use messages of exponential size. Show more

Keywords: Distributed Algorithm, AsynchronousMessage Passing Model, Anonymous Network, Local Computation, Election, Naming, Covering

Citation: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 221-246, 2007

Authors: Moshkov, Mikhail Ju. | Skowron, Andrzej | Suraj, Zbigniew

Article Type: Research Article

Abstract: The minimal rules for information systems are often used for inducing data models by methods in which the optimization of models is based on the minimal length principle. We show that almost all information systems from a certain large class of information systems have relatively short minimal rules. However, the number of such rules is not polynomial in the number of attributes and the number of objects. This class consists of all binary information systems with …the number of objects polynomial in the number of attributes. Hence, for efficient inducing data models some filtration techniques in rule generation are necessary. In our further study we would like to extend our results for arbitrary information systems. Show more

Keywords: Information systems, minimal rules, irreducible inconsistent systems of equations

Citation: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 247-258, 2007

Authors: Ochmański, Edward | Pieckowska, Joanna

Article Type: Research Article

Abstract: We extend the well-known hierarchy ∞-fair ⊆ 0-fair ⊆ just for sequences (sequential computations) to that of traces (concurrent processes). The fairness hierarchy for traces is similar, but more involved than for sequences. We study this hierarchy, first in general, abstracting from concrete concurrent system, then for basic classes of Petri nets – elementary and place/transition nets. Finally, we define the fairness notions in a non-interleaving way and compare them with the former ones.

Citation: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 259-272, 2007

Authors: Reisig, Wolfgang

Article Type: Research Article

Abstract: Concurrent runs reveal more insight into distributed systems than interleaved runs. This is shown by help of Dijkstra's paradigm of five philosophers.

Citation: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 273-281, 2007

Authors: Wang, Xu | Kwiatkowska, Marta

Article Type: Research Article

Abstract: Asynchronous circuits have received much attention recently due to their potential for energy savings. Process algebras have been extensively used in the modelling, analysis and synthesis of asynchronous circuits. This paper develops a theoretical basis for using process algebra and associated model checking tools to verify asynchronous circuits. We formulate a model that extends existing verification theory for asynchronous circuits, and integrate it into the framework of standard process algebra theory. Our theory permits …analysis of safeness (i.e. choke) and progress (i.e. illegal stop, divergence and relative starvation) conditions. We show how the model can be translated into CSP, and how the satisfaction of safeness and progress requirements can be reduced to refinement checks in CSP. Finally, the correspondence of our theory with trace theory (i.e. prefix-closed trace structures), receptive process theory and the XDI model is investigated. Show more

Keywords: Process algebra, asynchronous circuits, assume/guarantee verification, progress/liveness, and CSP/FDR2

Citation: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 283-310, 2007

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: The paper is devoted to characterizing hybrid systems by specifying their possible runs, called processes, where each process is represented by a pomset in an intrinsic, global time independent way and can possibly be obtained by composing sequentially and in parallel other processes.

Keywords: Hybrid systems, processes, states, sequential composition, parallel composition, category, partial monoid, structure, random behaviour

Citation: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 311-332, 2007