Introduction to Probabilistic Concurrent Systems

• Autorzy: Abbes Samy

Identyfikatory

DOI

10.3233/FI-222133

• Języki publikacji: EN

Abstrakty

EN

The first part of the paper is an introduction to the theory of probabilistic concurrent systems under a partial order semantics. Key definitions and results are given and illustrated on examples. The second part includes contributions. We introduce deterministic concurrent systems as a subclass of concurrent systems. Deterministic concurrent system are “locally commutative” concurrent systems. We prove that irreducible and deterministic concurrent systems have a unique probabilistic dynamics, and we characterize these systems by means of their combinatorial properties.

Słowa kluczowe

EN

Computer Science - Formal Languages and Automata Theory; G.2.1,F.1.1

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: vol. 187 nr 2-4
• Strony: 71--102
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Abbes Samy

• Laboratoire IRIF, Université Paris Cité Paris, France

Bibliografia

• [1] Diekert V. Combinatorics on Traces. Springer, 1990. ISBN-13:978-3540530312, 10:3540530312.
• [2] Diekert V, Rozenberg G (eds.). The Book of Traces. World Scientific, 1995. doi:10.1142/2563.
• [3] Abbes S. Markovian dynamics of concurrent systems. Discrete Event Dyn. Syst., 2019. 29(4):527-566. doi:10.1007/s10626-019-00291-z.
• [4] Reisig W. Petri Nets. An Introduction. Springer, 1985. doi:10.1007/978-3-642-69968-9.
• [5] Nielsen M, G P, Winskel G. Petri nets, event structures and domains, part I. Theoret. Comput. Sci., 1981. 13(1):85-108. doi:10.1016/0304-3975(81)90112-2.
• [6] Abbes S, Mairesse J. Uniform and Bernoulli measures on the boundary of trace monoids. J. Combin. Theory Ser. A, 2015. 135:201-236. doi:10.1016/j.jcta.2015.05.003.
• [7] Cartier P, Foata D. Problèmes combinatoires de commutation et réarrangements, volume 85 of Lecture Notes in Math. Springer, 1969.
• [8] Viennot X. Heaps of pieces, I : basic definitions and combinatorial lemmas. In: Combinatoire énumérative, volume 1234 of Lecture Notes in Math., pp. 321-350. Springer, 1986. doi:10.1007/BFb0072524.
• [9] Abbes S, Mairesse J, Chen YT. A spectral property for concurrent systems and some probabilistic applications. Discrete Mathematics, 2021. 344(8). 112455. doi:10.1016/j.disc.2021.112455.
• [10] Dehornoy P, Digne F, Godelle E, Krammer D, Michel J. Foundations of Garside Theory. EMS, 2015. ISBN:978-3-03719-139-2.
• [11] Book R, Otto F. String-rewriting Systems. Springer, 1993. doi:10.1007/978-1-4613-9771-7.
• [12] Krattenthaler C. The theory of heaps and the Cartier-Foata monoid. Appendix to the republication of [7] in Séminaire Lotharingien de Combinatoire, 2006. ID:3137291.
• [13] Epstein D, Cannon J, Holt D, Levy S, Paterson M, Thurston W. Word Processing in Groups. Jones and Bartlett, 1992. ISBN-13:978-0867202441, 10:0867202440.
• [14] Billingsley P. Probability and Measure. Wiley, 1995.
• [15] Rota GC. On the foundations of combinatorial theory I. Theory of Möbius functions. Z. Wahrschein-lichkeitstheorie, 1964. 2:340-368.
• [16] Krob D, Mairesse J, Michos I. Computing the average parallelism in trace monoids. Discrete Math., 2003. 273(1-3):131-162. doi:10.1016/S0012-365X(03)00233-4.
• [17] Goldwurm M, Santini M. Clique polynomials have a unique root of smallest modulus. Inform. Process. Lett., 2000. 75(3):127-132. doi:10.1016/S0020-0190(00)00086-7.