8 Search Results for "David, Julien"

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-dev.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
Artifact
DOI: 10.4230/DARTS.6.2.18
Multiparty Session Programming with Global Protocol Combinators (Artifact)

Authors: Keigo Imai, Rumyana Neykova, Nobuko Yoshida, and Shoji Yuen

Published in: DARTS, Volume 6, Issue 2, Special Issue of the 34th European Conference on Object-Oriented Programming (ECOOP 2020)

Abstract
In the paper "Multiparty Session Programming with Global Protocol Combinators", we introduce a library, ocaml-mpst for programming with global combinators - a set of functions for writing and verifying multiparty protocols in OCaml. Local behaviours for all processes in a protocol are inferred at once from a global combinator. Our approach enables fully-static verification and implementation of the whole protocol, from the protocol specification to the process implementations, to happen in the same language. This artifact is the source code of ocaml-mpst, with all the examples and benchmarks discussed in the paper.
Cite as

Keigo Imai, Rumyana Neykova, Nobuko Yoshida, and Shoji Yuen. Multiparty Session Programming with Global Protocol Combinators (Artifact). In Special Issue of the 34th European Conference on Object-Oriented Programming (ECOOP 2020). Dagstuhl Artifacts Series (DARTS), Volume 6, Issue 2, pp. 18:1-18:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Article{imai_et_al:DARTS.6.2.18,
  author =	{Imai, Keigo and Neykova, Rumyana and Yoshida, Nobuko and Yuen, Shoji},
  title =	{{Multiparty Session Programming with Global Protocol Combinators (Artifact)}},
  pages =	{18:1--18:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2020},
  volume =	{6},
  number =	{2},
  editor =	{Imai, Keigo and Neykova, Rumyana and Yoshida, Nobuko and Yuen, Shoji},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.6.2.18},
  URN =		{urn:nbn:de:0030-drops-132159},
  doi =		{10.4230/DARTS.6.2.18},
  annote =	{Keywords: Multiparty Session Types, Communication Protocol, Concurrent and Distributed Programming, OCaml}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.32
Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations

Authors: David Cohen-Steiner, André Lieutier, and Julien Vuillamy

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
This paper considers a particular case of the Optimal Homologous Chain Problem (OHCP) for integer modulo 2 coefficients, where optimality is meant as a minimal lexicographic order on chains induced by a total order on simplices. The matrix reduction algorithm used for persistent homology is used to derive polynomial algorithms solving this problem instance, whereas OHCP is NP-hard in the general case. The complexity is further improved to a quasilinear algorithm by leveraging a dual graph minimum cut formulation when the simplicial complex is a pseudomanifold. We then show how this particular instance of the problem is relevant, by providing an application in the context of point cloud triangulation.
Cite as

David Cohen-Steiner, André Lieutier, and Julien Vuillamy. Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohensteiner_et_al:LIPIcs.SoCG.2020.32,
  author =	{Cohen-Steiner, David and Lieutier, Andr\'{e} and Vuillamy, Julien},
  title =	{{Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.32},
  URN =		{urn:nbn:de:0030-drops-121908},
  doi =		{10.4230/LIPIcs.SoCG.2020.32},
  annote =	{Keywords: OHCP, simplicial homology, triangulation, Delaunay}
}
Document
DOI: 10.4230/LIPIcs.TIME.2019.15
A Bounded Domain Property for an Expressive Fragment of First-Order Linear Temporal Logic

Authors: Quentin Peyras, Julien Brunel, and David Chemouil

Published in: LIPIcs, Volume 147, 26th International Symposium on Temporal Representation and Reasoning (TIME 2019)

Abstract
First-Order Linear Temporal Logic (FOLTL) is well-suited to specify infinite-state systems. However, FOLTL satisfiability is not even semi-decidable, thus preventing automated verification. To address this, a possible track is to constrain specifications to a decidable fragment of FOLTL, but known fragments are too restricted to be usable in practice. In this paper, we exhibit various fragments of increasing scope that provide a pertinent basis for abstract specification of infinite-state systems. We show that these fragments enjoy the Bounded Domain Property (any satisfiable FOLTL formula has a model with a finite, bounded FO domain), which provides a basis for complete, automated verification by reduction to LTL satisfiability. Finally, we present a simple case study illustrating the applicability and limitations of our results.
Cite as

Quentin Peyras, Julien Brunel, and David Chemouil. A Bounded Domain Property for an Expressive Fragment of First-Order Linear Temporal Logic. In 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 147, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{peyras_et_al:LIPIcs.TIME.2019.15,
  author =	{Peyras, Quentin and Brunel, Julien and Chemouil, David},
  title =	{{A Bounded Domain Property for an Expressive Fragment of First-Order Linear Temporal Logic}},
  booktitle =	{26th International Symposium on Temporal Representation and Reasoning (TIME 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-127-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{147},
  editor =	{Gamper, Johann and Pinchinat, Sophie and Sciavicco, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2019.15},
  URN =		{urn:nbn:de:0030-drops-113731},
  doi =		{10.4230/LIPIcs.TIME.2019.15},
  annote =	{Keywords: First-Order Linear Temporal Logic, Bounded Domain Property, Finite Domain Property, Decidability}
}
Document
DOI: 10.4230/LIPIcs.CPM.2018.17
On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure

Authors: Guillaume Fertin, Julien Fradin, and Christian Komusiewicz

Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

Abstract
Let G=(V,A) be a vertex-colored arc-weighted directed acyclic graph (DAG) rooted in some vertex r. The color hierarchy graph H(G) of G is defined as follows: the vertex set of H(G) is the color set C of G, and H(G) has an arc from c to c' if G has an arc from a vertex of color c to a vertex of color c'. We study the Maximum Colorful Arborescence (MCA) problem, which takes as input a DAG G such that H(G) is also a DAG, and aims at finding in G a maximum-weight arborescence rooted in r in which no color appears more than once. The MCA problem models the de novo inference of unknown metabolites by mass spectrometry experiments. Although the problem has been introduced ten years ago (under a different name), it was only recently pointed out that a crucial additional property in the problem definition was missing: by essence, H(G) must be a DAG. In this paper, we further investigate MCA under this new light and provide new algorithmic results for this problem, with a focus on fixed-parameter tractability (FPT) issues for different structural parameters of H(G). In particular, we develop an O^*(3^{{x_H}})-time algorithm for solving MCA, where {x_{H}} is the number of vertices of indegree at least two in H(G), thereby improving the O^*(3^{|C|})-time algorithm of Böcker et al. [Proc. ECCB '08]. We also prove that MCA is W[2]-hard with respect to the treewidth t_H of the underlying undirected graph of H(G), and further show that it is FPT with respect to t_H + l_{C}, where l_{C} := |V| - |C|.
Cite as

Guillaume Fertin, Julien Fradin, and Christian Komusiewicz. On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fertin_et_al:LIPIcs.CPM.2018.17,
  author =	{Fertin, Guillaume and Fradin, Julien and Komusiewicz, Christian},
  title =	{{On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure}},
  booktitle =	{29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Navarro, Gonzalo and Sankoff, David and Zhu, Binhai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.17},
  URN =		{urn:nbn:de:0030-drops-86939},
  doi =		{10.4230/LIPIcs.CPM.2018.17},
  annote =	{Keywords: Subgraph problem, computational complexity, algorithms, fixed-parameter tractability, kernelization}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2015.283
Meeting Deadlines Together

Authors: Laura Bocchi, Julien Lange, and Nobuko Yoshida

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

Abstract
This paper studies safety, progress, and non-zeno properties of Communicating Timed Automata (CTAs), which are timed automata (TA) extended with unbounded communication channels, and presents a procedure to build timed global specifications from systems of CTAs. We define safety and progress properties for CTAs by extending properties studied in communicating finite-state machines to the timed setting. We then study non-zenoness for CTAs; our aim is to prevent scenarios in which the participants have to execute an infinite number of actions in a finite amount of time. We propose sound and decidable conditions for these properties, and demonstrate the practicality of our approach with an implementation and experimental evaluations of our theory.
Cite as

Laura Bocchi, Julien Lange, and Nobuko Yoshida. Meeting Deadlines Together. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 283-296, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bocchi_et_al:LIPIcs.CONCUR.2015.283,
  author =	{Bocchi, Laura and Lange, Julien and Yoshida, Nobuko},
  title =	{{Meeting Deadlines Together}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{283--296},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.283},
  URN =		{urn:nbn:de:0030-drops-53838},
  doi =		{10.4230/LIPIcs.CONCUR.2015.283},
  annote =	{Keywords: timed automata, multiparty session types, global specification}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.88
Asymptotic enumeration of Minimal Automata

Authors: Frédérique Bassino, Julien David, and Andrea Sportiello

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We determine the asymptotic proportion of minimal automata, within n-state accessible deterministic complete automata over a k-letter alphabet, with the uniform distribution over the possible transition structures, and a binomial distribution over terminal states, with arbitrary parameter b. It turns out that a fraction ~ 1-C(k,b) n^{-k+2} of automata is minimal, with C(k,b) a function, explicitly determined, involving the solution of a transcendental equation.
Cite as

Frédérique Bassino, Julien David, and Andrea Sportiello. Asymptotic enumeration of Minimal Automata. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 88-99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bassino_et_al:LIPIcs.STACS.2012.88,
  author =	{Bassino, Fr\'{e}d\'{e}rique and David, Julien and Sportiello, Andrea},
  title =	{{Asymptotic enumeration of Minimal Automata}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{88--99},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.88},
  URN =		{urn:nbn:de:0030-drops-34328},
  doi =		{10.4230/LIPIcs.STACS.2012.88},
  annote =	{Keywords: minimal automata, regular languages, enumeration of random structures}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1822
On the Average Complexity of Moore's State Minimization Algorithm

Authors: Frederique Bassino, Julien David, and Cyril Nicaud

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with $n$ states, the average complexity of Moore's state minimization algorithm is in $\mathcal{O}(n \log n)$. Moreover this bound is tight in the case of unary automata.
Cite as

Frederique Bassino, Julien David, and Cyril Nicaud. On the Average Complexity of Moore's State Minimization Algorithm. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 123-134, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bassino_et_al:LIPIcs.STACS.2009.1822,
  author =	{Bassino, Frederique and David, Julien and Nicaud, Cyril},
  title =	{{On the Average Complexity of Moore's State Minimization Algorithm}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{123--134},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1822},
  URN =		{urn:nbn:de:0030-drops-18222},
  doi =		{10.4230/LIPIcs.STACS.2009.1822},
  annote =	{Keywords: Finite automata, State minimization, Moore’s algorithm, Average complexity}
}
  • Refine by Author
  • 2 David, Julien
  • 2 Yoshida, Nobuko
  • 1 Bassino, Frederique
  • 1 Bassino, Frédérique
  • 1 Bocchi, Laura
  • Show More...

  • Refine by Classification
  • 1 Information systems → Data compression
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Generating functions
  • 1 Software and its engineering → Concurrent programming structures
  • Show More...

  • Refine by Keyword
  • 1 Average complexity
  • 1 Boolean Function
  • 1 Bounded Domain Property
  • 1 Communication Protocol
  • 1 Concurrent and Distributed Programming
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2020
  • 1 2009
  • 1 2012
  • 1 2015
  • 1 2018
  • Show More...

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 Imprint Privacy Contact