Uniform and Bernoulli measures on the boundary of trace monoids
| Autor: | Samy Abbes, Jean Mairesse |
|---|---|
| Přispěvatelé: | Preuves, Programmes et Systèmes (PPS), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Programmes et Résolution (APR), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Polynomial
Probability (math.PR) Probabilistic logic Boundary (topology) Random heaps Trace monoid Möbius polynomial Theoretical Computer Science Algebra 05D40 60C05 05A15 68Q85 Bernoulli's principle Computational Theory and Mathematics Bernoulli distribution [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Uniform measure Combinatorics (math.CO) Mathematics - Probability Probability measure Mathematics TRACE (psycholinguistics) |
| Zdroj: | Journal of Combinatorial Theory, Series A Journal of Combinatorial Theory, Series A, 2015, 135, pp.201-236. ⟨10.1016/j.jcta.2015.05.003⟩ Journal of Combinatorial Theory, Series A, Elsevier, 2015, 135, pp.201-236. ⟨10.1016/j.jcta.2015.05.003⟩ |
| ISSN: | 0097-3165 1096-0899 |
| DOI: | 10.1016/j.jcta.2015.05.003⟩ |
| Popis: | 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\"obius polynomial in the key role. These new measures provide a theoretical foundation for the probabilistic study of concurrent systems. Comment: 34 pages, 5 figures, 27 references |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect