Uniform and Bernoulli measures on the boundary of trace monoids
arXiv:1407.5879 · doi:10.1016/j.jcta.2015.05.003
Abstract
Trace monoids and heaps of pieces appear in various contexts in combinatorics. They also constitute a model used in computer science to describe the executions of asynchronous systems. The design of a natural probabilistic layer on top of the model has been a long standing challenge. The difficulty comes from the presence of commuting pieces and from the absence of a global clock. In this paper, we introduce and study the class of Bernoulli probability measures that we claim to be the simplest adequate probability measures on infinite traces. For this, we strongly rely on the theory of trace combinatorics with the Möbius polynomial in the key role. These new measures provide a theoretical foundation for the probabilistic study of concurrent systems.
arXiv comment34 pages, 5 figures, 27 references
Cited by in corpus (9)
- Markovian dynamics of concurrent systems
- Toward uniform random generation in 1-safe Petri nets
- Asymptotic combinatorics of Artin-Tits monoids and of some other monoids
- A spectral property for concurrent systems and some probabilistic applications
- Uniform measures on braid monoids and dual braid monoids
- Synchronization of Bernoulli sequences on shared letters
- Introduction to probabilistic concurrent systems
- Ergodic properties of concurrent systems
- Uniform generation of infinite concurrent runs: the case of trace monoids