Affordable Access

Access to the full text

A spectral property for concurrent systems and some probabilistic applications

Authors
  • Abbes, Samy
  • Mairesse, Jean
  • Chen, Yi-Ting
Type
Preprint
Publication Date
Apr 25, 2021
Submission Date
Mar 08, 2020
Identifiers
DOI: 10.1016/j.disc.2021.112455
Source
arXiv
License
Yellow
External links

Abstract

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

Statistics

Seen <100 times