• Introduction to probabilistic concurrent systems. Fundamenta Informaticae, 187(2-4):71–102, 2022
  Extended version of the paper Deterministic concurrent systems published in the conference Petri Nets 2021
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  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.

  @Article{,
  author = {Abbes, S.},
  title = {Introduction to probabilistic concurrent systems},
  journal = {Fundamenta Informaticae},
  volume = {},
  number = {},
  year = {2022}
  }
• A spectral property for concurrent systems and some probabilistic applications. Discrete Mathematics, 344(8), 2021. With J. Mairesse et Y.-T. Chen.
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  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.

  @Article{,
  author = {Abbes, S. and Mairesse, J. and Chen, Y.-T.},
  title = {A spectral property for concurrent systems and some probabilistic applications},
  journal = {Discrete Mathematics},
  volume = {344},
  number = {8},
  year = {2021}
  }
• Markovian dynamics of concurrent systems. Discrete Event Dynamic Systems, 29(4):527-566, 2019.
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  Monoid actions of trace monoids over finite sets are powerful models of concurrent systems---for instance they encompass the class of 1-safe Petri nets.
  We characterise Markov measures attached to concurrent systems by finitely many parameters with suitable normalisation conditions. These conditions involve polynomials related to the combinatorics of the monoid and of the monoid action. These parameters generalise to concurrent systems the coefficients of the transition matrix of a Markov chain.
  A natural problem is the existence of the uniform measure for every concurrent system. We prove this existence under an irreducibility condition. The uniform measure of a concurrent system is characterised by a real number, the characteristic root of the action, and a function of pairs of states, the Parry cocyle. A new combinatorial inversion formula allows to identify a polynomial of which the characteristic root is the smallest positive root. Examples based on simple combinatorial tilings are studied.

  @Article{,
  author = {Abbes, S.},
  title = {Markovian dynamics of concurrent systems},
  journal = {Discrete Event Dynamic Systems},
  volume={29},
  number={4},
  pages={27--566},
  year = 2019,
  doi = {10.1007/s10626-019-00291-z}
  }
• Asymptotic combinatorics of Artin-Tits monoids and of some other monoids. Journal of Algebra, 525:497-561, 2019. With S. Gouëzel, V. Jugé and J. Mairesse.
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We introduce methods to study the combinatorics of the normal form of large random elements in Artin-Tits monoids. These methods also apply in an axiomatic framework that encompasses other monoids such as dual braid monoids.

  @Article{,
  author = {Abbes, S. and Gou\"ezel, S. and Jug\'e, V. and Mairesse, J.},
  title = {Asymptotic combinatorics of Artin-Tits monoids and of some other monoids},
  journal = {Journal of Algebra},
  year = 2019,
  volume = {525},
  pages = {497--561},
  doi = {10.1016/j.jalgebra.2019.01.019}
  }
• Synchronization of Bernoulli sequences on shared letters. Information and Computation, 255(1):1-26, 2017.
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  The topic of this paper is the distributed and incremental generation of long executions of concurrent systems, uniformly or more generally with weights associated to elementary actions. Synchronizing sequences of letters on alphabets sharing letters are known to produce a trace in the concurrency theoretic sense, i.e., a labeled partially ordered set. We study the probabilistic aspects by considering the synchronization of Bernoulli sequences of letters, under the light of Bernoulli and uniform measures recently introduced for trace monoids. We introduce two algorithms that produce random traces, using only local random primitives. We thoroughly study some specific examples, the path model and the ring model, both of arbitrary size. For these models, we show how to generate any Bernoulli distributed random traces, which includes the case of uniform generation.

  @Article{,
  author = {Abbes, S.},
  title = {Synchronization of Bernoulli sequences on shared letters},
  journal = {Information and Computation},
  year = 2017,
  volume = {255},
  number = {1},
  pages = {1--26},
  doi = {10.1016/j.ic.2017.04.002}
  }
• Uniform measures on braid monoids and dual braid monoids. Journal of Algebra, 473(1):627-666, 2017. With S. Gouëzel, V. Jugé and J. Mairesse.
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We aim at studying the asymptotic properties of typical positive braids, respectively positive dual braids. Denoting by μk the uniform distribution on positive (dual) braids of length k , we prove that the sequence (μk)k converges to a unique probability measure μ∞ on infinite positive (dual) braids. The key point is that the limiting measure μ∞ has a Markovian structure which can be described explicitly using the combinatorial properties of braids encapsulated in the Möbius polynomial. As a by-product, we settle a conjecture by Gebhardt and Tawn (J. Algebra, 2014) on the shape of the Garside normal form of large uniform braids.

  @Article{,
  author = {Abbes, S. and Gou\"zel, S. and Jug\'e, V. and Mairesse, J.},
  title = {Uniform measures on braid monoids and dual braid monoids},
  journal = {Journal of Algebra},
  year = 2017,
  volume = {473},
  number = {1},
  pages = {627--666},
  doi = {10.1007/s10959-016-0692-6}
  }
• A cut-invariant law of large numbers for random heaps. Journal of Theoretical Probability, 30(4):1692-1725, 2017
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We consider the framework of Bernoulli measures for heap monoids. We introduce in this framework the notion of asynchronous stopping time, which generalizes the notion of stopping time for classical probabilistic processes. A Strong Bernoulli property is proved. A notion of cut-invariance is formulated for convergent ergodic means. Then a version of the Strong law of large numbers is proved for heap monoids with Bernoulli measures. We study a sub-additive version of the Law of large numbers in this framework.

  @Article{,
  author = {Abbes, S.},
  title = {A cut-invariant law of large numbers for random heaps},
  journal = {Journal of Theoretical Probability},
  year = 2017,
  number = {30},
  volume = {4},
  pages = {1692--1725},
  doi = {10.1007/s10959-016-0692-6}
  }
• Uniform and Bernoulli measures on the boundary of trace monoids. Journal of Combinatorial Theory, Series A 135:201-236, 2015. With J. Mairesse.
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  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.

  @Article{,
  author = {Abbes, S. and Mairesse, J.},
  title = {Uniform and Bernoulli measures on the boundary of trace monoids},
  journal = {Journal of Combinatorial Theory, Series A},
  year = 2015,
  number = {135},
  pages = {201--236},
  doi = {10.1016/j.jcta.2015.05.003}
  }
• Markov two-components processes. Logical Methods in Computer Science 9(2:14):1-34, 2013.
  DOI - arXiv - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We propose Markov two-components processes (M2CP) as a probabilistic model of asynchronous systems based on the trace semantics for concurrency. Considering an asynchronous system distributed over two sites, we introduce concepts and tools to manipulate random trajectories in an asynchronous framework: stopping times, an Asynchronous Strong Markov property, recurrent and transient states and irreducible components of asynchronous probabilistic processes. The asynchrony assumption implies that there is no global totally ordered clock ruling the system. Instead, time appears as partially ordered and random. We construct and characterize M2CP through a finite family of transition matrices. M2CP have a local independence property that guarantees that local components are independent in the probabilistic sense, conditionally to their synchronization constraints. A synchronization product of two Markov chains is introduced, as a natural example of M2CP.

  @Article{abbes13,
  author = {Abbes, S.},
  title = {Markov two-components processes},
  journal = {Logical Methods in Computer Science},
  year = 2013,
  month = {June},
  number = {9(2:14)},
  pages = {1--34},
  doi = {10.2168/LMCS-9(2:14)2013}
  }
• On countable completions of quotient ordered semigroups. Semigroup Forum 77(3):482-499, 2008.
  DOI - HAL - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We study the commutativity of two operations: quotienting and completing. Completing refers to the countable chain completion, known to exist in every partial order, and quotienting is with respect to a semigroup congruence. The two operations are shown to commute in a suitable framework. We apply the results for studying the semigroup structure and topological semigroup structure on the completion.

  @Article{abbes08,
  author = {Abbes, S.},
  title = {{On Countable Completions of Quotient Ordered Semigroups}},
  journal = {Semigroup Forum},
  year = 2008,
  month = {December},
  number = {77},
  volume = {3},
  pages = {482--499}
  }
• Probabilistic true-concurrency models: Markov nets and a Law of large numbers. Theoretical Computer Science 390(2-3):129-170, 2008. With A. Benveniste.
  DOI - HAL - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We introduce the model of Markov nets, a probabilistic extension of safe Petri nets under the true-concurrency semantics. This means that traces, not firing sequences, are given a probability. This model builds upon our previous work on probabilistic event structures. We use the notion of branching cell for event structures and show that the latter provides the adequate notion of local state, for nets. We prove a Law of Large Numbers (LLN) for Markov nets, which constitutes the main contribution of the paper. This LLN allows characterizing in a quantitative way the asymptotic behavior of Markov nets.

  @Article{abbes07b,
  author = {Abbes, S. and Benveniste, A.},
  title = {{Probabilistic true-concurrency models: Markov nets and a law of large numbers}},
  journal = {Theoretical Computer Science},
  year = 2008,
  volume = {390},
  number = {2-3},
  pages = {129--170}
  }
• A projective formalism applied to topological and probabilistic event structures. Mathematical Structures in Computer Science 17(4):819-837, 2007.
  DOI - HAL - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  This paper introduces projective systems for topological and probabilistic event structures. The projective formalism is used for studying the domain of configurations of a prime event structure and its space of maximal elements. This is done from both a topological and a probabilistic viewpoint. We give probability measure extension theorems in this framework.

  @Article{abbes07a,
  author = {Abbes, S.},
  title = {A projective formalism applied to topological and probabilistic event structures},
  journal = {Mathematical Structures in Computer Science},
  year = 2007,
  volume = 17,
  number = 4,
  pages = {819--837}}
• Projective topology on bifinite domains and applications. Theoretical Computer Science 365(3):171-183, 2006. With K. Keimel.
  DOI - HAL - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We revisit extension results from continuous valuations to Radon measures for bifinite domains. In the framework of bifinite domains, the Prokhorov theorem (existence of projective limits of Radon measures) appears as a natural tool, and helps building a bridge between Measure theory and Domain theory. The study we present also fills a gap in the literature concerning the coincidence between projective and Lawson topology for bifinite domains. Motivated by probabilistic considerations, we study the extension of measures in order to define Borel measures on the space of maximal elements of a bifinite domain.

  @Article{abbes06c,
  author = {Abbes, S. and Keimel, K.},
  title = {Projective topology on bifinite domains and applications},
  journal = {Theoretical Computer Science},
  year = 2006,
  volume = 365,
  number = 3,
  pages = {171--183}}
• A Cartesian closed category of event structures with quotients. Discrete Mathematics and Theoretical Computer Science 8(1):249-272, 2006.
  DOI - HAL - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  We introduce a new class of morphisms for event structures. The category obtained is cartesian closed, and a natural notion of quotient event structure is defined within it. We study in particular the topological space of maximal configurations of quotient event structures. We introduce the compression of event structures as an example of quotient: the compression of an event structure E is a minimal event structure with the same space of maximal configurations as E.

  @Article{abbes06b,
  author = {Abbes, S.},
  title = {A Cartesian closed category of event structures with quotients},
  journal = {Discrete Mathematics and Theoretical Computer Science},
  year = 2006,
  volume = 8,
  number = 1,
  pages = {249--272}}
• Probabilistic models for true-concurrency: branching cells and distributed probabilities for event structures. Information and Computation 204(2):231-274, 2006. With A. Benveniste.
  DOI - HAL - PDF - (Show/Hide abstract) - (Show/Hide BibTeX references)

  This paper is devoted to probabilistic models for concurrent systems under their true-concurrency semantics. Here we address probabilistic event structures. We consider a new class of event structures, called locally finite, that extend confusion-free event structure. In locally finite event structures, maximal configurations can be tiled with branching cells: branching cells are minimal and finite sub-structures capturing the choices performed while scanning a maximal configuration. The probabilistic event structures that we introduce have the property that concurrent processes are independent in the probabilistic sense.

  @Article{abbes06a,
  author = {Abbes, S. and Benveniste, A.},
  title = {Probabilistic true-concurrency models: branching cells and distributed probabilities for event structures},
  journal = {Information and Computation},
  year = 2006,
  volume = 204,
  number = 2,
  pages = {231--274}}

Conference publications

• Convergence of distributions on paths. In H. Fernau and K. Jansen, editors, Fundamentals of Computation Theory (Proccedings of FCT 2023, Trier, Germany), LNCS, volume 14292, p.1-15, 2023
  DOI - (Afficher/Cacher les références BibTeX)
  @InProceedings{, author = {Abbes, S.},
  title = {Convergence of distributions on paths},
  booktitle = {Fundamentals of Computation Theory (FCT 2023)},
  year = 2023,
  editor = {Fernau, H. and Jansen, K.},
  volume = 14292,
  series = {LNCS},
  pages = {1--15},
  publisher = {Springer}}
• Uniform generation of infinite traces. In L. Ferrari and P. Massazza, editors, Pure Mathematics and Applications, volume 30, issue 1, p. 1-7, 2022 (GASCom 2022). With V. Jugé
  DOI - arXiv (extended version) - (Show/Hide BibTeX references)
  @InProceedings{,
  author = {Abbes, S. and Jugé, V.},
  title = {Uniform generation of infinite traces},
  journal = {Pure Mathematics and Applications},
  number = {1},
  volume = {30},
  year = {2022},
  pages = {1--7},
  doi = {doi:10.2478/puma-2022-0002}}
• Deterministic concurrent systems. In D. Buchs and J. Carmona, editors, Application and Theory of Petri Nets and Concurrency. Petri Nets 2021, LNCS 12734, p.423-442. Springer, 2021.
  DOI - arXiv - HAL - (Show/Hide BibTeX references)
  @InProceedings{,
  author = {Abbes, S.},
  title = "Deterministic concurrent systems",
  editor = "Buchs, J. and Carmona, J.",
  series = "LNCS",
  volume = "12734",
  pages = "423--442",
  year = "2021",
  booktitle = "Application and Theory of Petri Nets and Concurrency. Petri Nets 2021",
  doi = "10.1007/978-3-030-76983-3_21"}
  
• Toward uniform random generation in 1-safe Petri nets. In J.-M. Fédou and L. Ferrari, editoris, Random generation of combinatorial structures - GASCOM 2016, Electronic Notes in Discrete Mathematics, volume 59, p. 3-17, 2017.
  DOI - arXiv - HAL - (Show/Hide BibTeX references)
  @InProceedings{,
  author = {Abbes, S.},
  title = "Toward uniform random generation in 1-safe {P}etri nets ",
  editor = "F\'edou, J.-M. and Ferrari, L.",
  series = "Electronic Notes in Discrete Mathematics ",
  volume = "59",
  pages = "3--17",
  year = "2017",
  booktitle = "Random Generation of Combinatorial Structures -- GASCom 2016",
  doi = "10.1016/j.endm.2017.05.002"}
  
• Uniform generation in trace monoids. In G. Italiano, G. Pighizzini and D. Sannella (Eds), MFCS 2015, Mathematical Foundations of Computer Science 2015, Part 1. Volume 9234 of LNCS, Springer, p. 63-75, 2015. With J. Mairesse.
  DOI - arXiv - (Show/Hide BibTeX references)
  @InProceedings{,
  author = {Abbes, S. and Mairesse, J.},
  title = {Uniform generation in trace monoids},
  booktitle = {Mathematical Foundations of Computer Science 2015 (MFCS 2015), part 1},
  editor = {Italiano, G. and Pighizzini, G. and Sannella, D.},
  year = 2015,
  volume = 9234,
  series= {LNCS},
  publisher={Springer},
  pages = {63--75}}
  
• Concurrency, sigma-algebras and probabilistic fairness. In L. de Alfaro, editor, FOSSACS 2009, 12th Conference on Foundation of Software Science and Computation Structures, member of ETAPS 2009, York (UK), volume 5504 of LNCS, p. 380-394, 2009. With A. Benveniste.
  DOI - PDF - (Show/Hide BibTeX references)
  @InProceedings{,
  author = {Abbes, S. and Benveniste, A.},
  title = {Concurrency, sigma-algebras and probabilistic fairness},
  booktitle = {12th~Conference on Foundations of Software Science and Computation Structures (FOSSACS 09)},
  editor = {de Alfaro, L.},
  year = 2009,
  volume = 5504,
  series= {LNCS},
  publisher={Springer},
  pages = {380--394}}
  
  Version augmentée (2008) : HAL - PDF
• Branching cells as local states for event structures and nets: probabilistic applications. In V. Sassone, editor, FOSSACS 2005, Conference on Foundations of Software Science and Computation Structures, member of ETAPS 2005, Edimbourgh (UK), volume 3441 of LNCS, p. 95-109, 2005. With A. Benveniste.
  DOI - HAL - PDF - (Show/Hide BibTeX references)
  @InProceedings{,
  author = {Abbes, S. and Benveniste, A.},
  title = {Branching cells as local states for event structures and nets: probabilistic applications},
  booktitle = {Conference on Foundations of Software Science and Computation Structures (FOSSACS 05)},
  editor = {Sassone, V.},
  year = 2005,
  volume = 3441,
  series= {LNCS},
  pages = {95--109},
  address = {Edimburgh (UK)}}
  
  Version augmentée : rapport interne IRISA PI 1651, 2004 - Archive IRISA
• The (true) concurrent Markov property and some applications to Markov nets. In G. Ciardo and P. Darondeau, editors, ICATPN'05, International Conference on Theory and Applications of Petri Nets, Miami (FL, USA), volume 3536 of LNCS, p. 70-89, 2005.
  DOI - HAL - PDF - (Show/Hide BibTeX references)
  @InProceedings{,
  author = {Abbes, S.},
  title = {{The (true) concurrent Markov property and some applications to Markov nets}},
  booktitle = {International Conference on Theory and Applications of Petri Nets (ICATPN~05)},
  editor = {Ciardo, G. and Darondeau, P.},
  year = 2005,
  volume = 3536,
  series= {LNCS},
  pages = {70--89},
  address = {Miami (FL, USA)}}