Search Results

Documents authored by Genitrini, Antoine

Artifact
Software
DOI: 10.4230/artifacts.22472
Set Partition Unranking

Authors: Amaury Curiel and Antoine Genitrini

Abstract
Cite as

Amaury Curiel, Antoine Genitrini. Set Partition Unranking (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22472,
   title = {{Set Partition Unranking}}, 
   author = {Curiel, Amaury and Genitrini, Antoine},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:b01a69e78b0fd972fdafc0c080421688cd9c9be6;origin=https://github.com/AMAURYCU/setpartition_unrank;visit=swh:1:snp:f9a49d6aee1aa584fc947cfbe7d63150624f674b;anchor=swh:1:rev:6fe83b16cb6c88237b5345b8090cbe63d700463e}{\texttt{swh:1:dir:b01a69e78b0fd972fdafc0c080421688cd9c9be6}} (visited on 2024-11-28)},
   url = {https://github.com/AMAURYCU/setpartition_unrank},
   doi = {10.4230/artifacts.22472},
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.17
Lexicographic Unranking Algorithms for the Twelvefold Way

Authors: Amaury Curiel and Antoine Genitrini

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
The Twelvefold Way represents Rota’s classification, addressing the most fundamental enumeration problems and their associated combinatorial counting formulas. These distinct problems are connected to enumerating functions defined from a set of elements denoted by 𝒩 into another one 𝒦. The counting solutions for the twelve problems are well known. We are interested in unranking algorithms. Such an algorithm is based on an underlying total order on the set of structures we aim at constructing. By taking the rank of an object, i.e. its number according to the total order, the algorithm outputs the structure itself after having built it. One famous total order is the lexicographic order: it is probably the one that is the most used by people when one wants to order things. While the counting solutions for Rota’s classification have been known for years it is interesting to note that three among the problems have yet no lexicographic unranking algorithm. In this paper we aim at providing algorithms for the last three cases that remain without such algorithms. After presenting in detail the solution for set partitions associated with the famous Stirling numbers of the second kind, we explicitly explain how to adapt the algorithm for the two remaining cases. Additionally, we propose a detailed and fine-grained complexity analysis based on the number of bitwise arithmetic operations.
Cite as

Amaury Curiel and Antoine Genitrini. Lexicographic Unranking Algorithms for the Twelvefold Way. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{curiel_et_al:LIPIcs.AofA.2024.17,
  author =	{Curiel, Amaury and Genitrini, Antoine},
  title =	{{Lexicographic Unranking Algorithms for the Twelvefold Way}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.17},
  URN =		{urn:nbn:de:0030-drops-204522},
  doi =		{10.4230/LIPIcs.AofA.2024.17},
  annote =	{Keywords: Twelvefold Way, Set partitions, Unranking, Lexicographic order}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.36
An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams

Authors: Julien Clément and Antoine Genitrini

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
For three decades binary decision diagrams, a data structure efficiently representing Boolean functions, have been widely used in many distinct contexts like model verification, machine learning, cryptography and also resolution of combinatorial problems. The most famous variant, called reduced ordered binary decision diagram (robdd for short), can be viewed as the result of a compaction procedure on the full decision tree. A useful property is that once an order over the Boolean variables is fixed, each Boolean function is represented by exactly one robdd. In this paper we aim at computing the {exact distribution of the Boolean functions in k variables according to the robdd size}, where the robdd size is equal to the number of decision nodes of the underlying directed acyclic graph (dag) structure. Recall the number of Boolean functions with k variables is equal to 2^{2^k}, which is of double exponential growth with respect to the number of variables. The maximal size of a robdd with k variables is M_k ≈ 2^k / k. Apart from the natural combinatorial explosion observed, another difficulty for computing the distribution according to size is to take into account dependencies within the dag structure of robdds. In this paper, we develop the first polynomial algorithm to derive the distribution of Boolean functions over k variables with respect to robdd size denoted by n. The algorithm computes the (enumerative) generating function of robdds with k variables up to size n. It performs O(k n⁴) arithmetical operations on integers and necessitates storing O((k+n) n²) integers with bit length O(nlog n). Our new approach relies on a decomposition of robdds layer by layer and on an inclusion-exclusion argument.
Cite as

Julien Clément and Antoine Genitrini. An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{clement_et_al:LIPIcs.MFCS.2023.36,
  author =	{Cl\'{e}ment, Julien and Genitrini, Antoine},
  title =	{{An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.36},
  URN =		{urn:nbn:de:0030-drops-185702},
  doi =		{10.4230/LIPIcs.MFCS.2023.36},
  annote =	{Keywords: Boolean Function, Reduced Ordered Binary Decision Diagram (\{robdd\}), Enumerative Combinatorics, Directed Acyclic Graph}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.14
Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes

Authors: Olivier Bodini, Matthieu Dien, Antoine Genitrini, and Alfredo Viola

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allowing to delay some computations. The structure of a general concurrent process is a directed acyclic graph (DAG). Since the quantitative study of increasingly labeled DAG (directly related to processes) seems out of reach (this is a #P-complete problem), we restrict ourselves to the study of arch processes, a simplistic model of processes with futures. They are based on two parameters related to their sizes and their numbers of arches. The increasingly labeled structures seems not to be specifiable in the classical sense of Analytic Combinatorics, but we manage to derive a recurrence equation for the enumeration. For this model we first exhibit an exact and an asymptotic formula for the number of runs of a given process. The second main contribution is composed of a uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.
Cite as

Olivier Bodini, Matthieu Dien, Antoine Genitrini, and Alfredo Viola. Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bodini_et_al:LIPIcs.AofA.2018.14,
  author =	{Bodini, Olivier and Dien, Matthieu and Genitrini, Antoine and Viola, Alfredo},
  title =	{{Beyond Series-Parallel Concurrent Systems: The Case of Arch Processes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.14},
  URN =		{urn:nbn:de:0030-drops-89075},
  doi =		{10.4230/LIPIcs.AofA.2018.14},
  annote =	{Keywords: Concurrency Theory, Future, Uniform Random Sampling, Unranking, Analytic Combinatorics}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.425
The Combinatorics of Non-determinism

Authors: Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
A deep connection exists between the interleaving semantics of concurrent processes and increasingly labelled combinatorial structures. In this paper we further explore this connection by studying the rich combinatorics of partially increasing structures underlying the operator of non-deterministic choice. Following the symbolic method of analytic combinatorics, we study the size of the computation trees induced by typical non-deterministic processes, providing a precise quantitative measure of the so-called "combinatorial explosion" phenomenon. Alternatively, we can see non-deterministic choice as encoding a family of tree-like partial orders. Measuring the (rather large) size of this family on average offers a key witness to the expressiveness of the choice operator. As a practical outcome of our quantitative study, we describe an efficient algorithm for generating computation paths uniformly at random.
Cite as

Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski. The Combinatorics of Non-determinism. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 425-436, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bodini_et_al:LIPIcs.FSTTCS.2013.425,
  author =	{Bodini, Olivier and Genitrini, Antoine and Peschanski, Fr\'{e}d\'{e}ric},
  title =	{{The Combinatorics of Non-determinism}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{425--436},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.425},
  URN =		{urn:nbn:de:0030-drops-43901},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.425},
  annote =	{Keywords: Concurrency theory, Analytic combinatorics, Non-deterministic choice, Partially increasing trees, Uniform random generation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact