Forschungsleitung (Direction de recherche) : Antoine GENITRINI

Quantitative and algorithmic analysis of concurrent programs

In this thesis, we study the state space of concurrent programs using tools from analytic combinatorics. First, we study a class of programs featuring parallelism, non-deterministic choice, loops and a fork-join style of synchronisation. For this class, we propose quantitative results regarding the combinatorial explosion of the state space and efficient algorithmic tools for the uniform random generation of executions.
Then, we study a new class of directed acyclic graphs, which are related to the control-flow of concurrent programs as an encoding of partial orders. For this class, we propose a efficient uniform random sampling algorithm with a given number of edges and vertices.
Finally, we also study various algorithmic and practical aspects of random generation whose field of application goes beyond the scope of concurrency.

Publikationen 2020-2022

• 2022
  • A. Genitrini, M. Pépin, F. Peschanski : “A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space”, Theoretical Computer Science, vol. 912, pp. 1-36, (Elsevier) (2022)
• 2021
  • M. Pepin : “Quantitative and algorithmic analysis of concurrent programs”, these, verteidigung einer doktorarbeit 29.09.2021, forschungsleitung (direction de recherche) Genitrini, Antoine (2021)
  • A. Genitrini, M. Pépin : “Lexicographic unranking of combinations revisited”, Algorithms, vol. 14 (3), pp. 97, (MDPI) (2021)
  • A. Genitrini, M. Pépin, A. Viola : “Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling”, Procedia Computer Science, vol. 195, Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, Sao Paulo, Brazil, pp. 468-477, (Elsevier) (2021)
• 2020
  • A. Genitrini, M. Pépin, F. Peschanski : “Statistical Analysis of Non-Deterministic Fork-Join Processes”, Theoretical Aspects of Computing - ICTAC 2020 - 17^th International Colloquium, vol. 12545, Lecture Notes in Computer Science, Macau, China, pp. 83-102, (Springer) (2020)