The Ordered and Colored Products in Analytic Combinatorics: Application to the Quantitative Study of Synchronizations in Concurrent Processes
| Autor: | Matthieu Dien, Frédéric Peschanski, Olivier Bodini, Antoine Genitrini |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-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) |
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Extremal combinatorics Increasing Graph-Structures Class (set theory) Interpretation (logic) Concurrency Theory [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 010102 general mathematics 0102 computer and information sciences Join (topology) 01 natural sciences Algebra Set (abstract data type) Boxed Product Closure (mathematics) 010201 computation theory & mathematics Product (mathematics) Analytic combinatorics 0101 mathematics Analytic Combinatorics Mathematics |
| Zdroj: | ANALCO 2017 Proceedings of the Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) 14th Workshop on Analytic Algorithmics and Combinatorics (ANALCO17) 14th Workshop on Analytic Algorithmics and Combinatorics (ANALCO17), Jan 2017, Barcelone, Spain. pp.16-30, ⟨10.1137/1.9781611974775.2⟩ |
| DOI: | 10.1137/1.9781611974775.2 |
| Popis: | International audience; In this paper, we study two operators for composing combinatorial classes: the ordered product and its dual, the colored product. These operators have a natural interpretation in terms of Analytic Combinatorics, in relation with combinations of Borel and Laplace transforms. Based on these new constructions, we exhibit a set of transfer theorems and closure properties. We also illustrate the use of these operators to specify increasingly labeled structures tightly related to Series-Parallel constructions and concurrent processes. In particular, we provide a quantitative analysis of Fork/Join (FJ) parallel processes, a particularly expressive example of such a class. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|