HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Trellis Processes : a Compact Representation for Runs of Concurrent Systems

Eric Fabre 1
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : In the true concurrency semantics, runs of a concurrent system are represented as partial orders of events. To represent sets of such runs in a compact manner, traditional approaches rely on branching processes. The maximal branching process of a system, for the prefix relation, is known as the unfolding of that system. Unfoldings (of a finite complete prefix of them) are used for model-checking purposes, reachability analysis, system monitoring or diagnosis, etc. In particular, they enjoy nice factorization properties that allow the development of distributed/modular algorithms, for model checking or diagnosis. In this communication, we propose an alternate and somehow intermediate representation for runs of concurrent systems, where time is unfolded, but not the conflict relation. In few words, we abandon the requirement that no node of a branching process be in self-conflict, and allow confluence of conflicting histories. We obtain in that way trellis processes, and the time-unfolding of a system. The latter represents the same configuration set as the familiar unfolding, while being more compact in width. Moreover, trellis processes generalize to concurrent systems the usual notion of trellis of an automaton, which forms the support of most on-line monitoring algorithms. Through a suitable co-reflection of trellis nets in the category of safe nets, we finally prove that time-unfoldings enjoy the same factorization properties as standard unfoldings, which makes these more compact structures possible candidates for distributed verification/diagnosis algorithms.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:31:54 PM
Last modification on : Friday, February 4, 2022 - 3:22:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:15:15 PM


  • HAL Id : inria-00070452, version 1


Eric Fabre. Trellis Processes : a Compact Representation for Runs of Concurrent Systems. [Research Report] RR-5554, INRIA. 2005, pp.34. ⟨inria-00070452⟩



Record views


Files downloads