Trellis Processes : a Compact Representation for Runs of Concurrent Systems

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.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/inria-00070452
Author Fabre, Eric
Maintainer CCSD
Last Updated May 16, 2026, 02:42 (UTC)
Created May 16, 2026, 02:42 (UTC)
Identifier Report N°: RR-5554
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Distributed and Iterative Algorithms for the Management of Telecommunications Systems (DISTRIBCOM) ; Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) ; Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) ; Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes) ; Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de l'Université de Rennes ; Institut National de Recherche en Informatique et en Automatique (Inria)
creator Fabre, Eric
date 2005-05-16T00:00:00
harvest_object_id 8e102cc9-1bc3-486d-8f1c-c4d286ba4a70
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-03-28T00:00:00
set_spec type:REPORT