CV

PDF

Journal publications

• 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ëezel, 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 (Springer), 1-34, 2016.
  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 = 2016,
  pages = {1--34},
  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 for 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 formalisme 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.
  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

• Toward uniform random generation in 1-safe Petri nets. In Random generation of combinatorial structures - GASCOM 2016, J.-M. Fédou and L. Ferrari, editors, 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 ",
  series = "Electronic Notes in Discrete Mathematics ",
  editor = "F\'edou, J.-M. and Ferrari, L.",
  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},
  pages = {380--394},
  address = {York (UK)}}
  
  Extended version (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)}}
  
  Extended version: preprint IRISA PI 1651, 2004 - IRISA archive
  
• 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)}}

Research topics

• Combinatorics and probability: measure of maximal entropy, uniform measure, random generation.
• Models of algebraic combinatorics: heap monoids (Viennot's "heaps of pieces" which correspond to "right-angled" Coxeter-Tits monoids), positive braid monoids.
• Limits of finite combinatorial structures. Weak convergence of uniform distributions.
• Random generation in concurrent systems: trace monoids, trace languages, Petri nets.

Co-authors

• Albert Benveniste
• Sébastien Gouëzel
• Vincent Jugé
• Klaus Keimel
• Jean Mairesse