Affordable Access

Access to the full text

A spectral property for concurrent systems and some probabilistic applications

  • Abbes, Samy
  • Mairesse, Jean
  • Chen, Yi-Ting
Publication Date
Apr 25, 2021
Submission Date
Mar 08, 2020
DOI: 10.1016/j.disc.2021.112455
External links


We study trace theoretic concurrent systems. This setting encompasses safe (1-bounded) Petri nets. We introduce a notion of irreducible concurrent system and we prove the equivalence between irreducibility and a "spectral property". The spectral property states a strict inequality between radii of convergence of certain growth series associated with the system. The proof that we present relies on analytic combinatorics techniques. The spectral property is the cornerstone of our theory, in a framework where the Perron-Frobenius theory does not apply directly. This restriction is an inherent difficulty in the study of concurrent systems. We apply the spectral property to the probabilistic theory of concurrent systems. We prove on the one hand the uniqueness of the uniform measure, a question left open in a previous paper. On the other hand, we prove that this uniform measure can be realized as a Markov chain of states-and-cliques on a state space that can be precisely characterized.

Report this publication


Seen <100 times