8 Search Results for "Perrot, Kevin"

Volume

OASIcs, Volume 90

27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

AUTOMATA 2021, July 12-14, 2021, Aix-Marseille University, France

Editors: Alonso Castillo-Ramirez, Pierre Guillon, and Kévin Perrot

Document
DOI: 10.4230/LIPIcs.WADS.2025.45
Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences

Authors: Tuyen Pham and Hubert Wagner

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
The contributions of the paper span theoretical and implementational results. First, we prove that Kd-trees can be extended to ℝ^d with the distance measured by an arbitrary Bregman divergence. Perhaps surprisingly, this shows that the triangle inequality is not necessary for correct pruning in Kd-trees. Second, we offer an efficient algorithm and C++ implementation for nearest neighbour search for decomposable Bregman divergences. The implementation supports the Kullback-Leibler divergence (relative entropy) which is a popular distance between probability vectors and is commonly used in statistics and machine learning. This is a step toward broadening the usage of computational geometry algorithms. Our benchmarks show that our implementation efficiently handles both exact and approximate nearest neighbour queries. Compared to a linear search, we achieve two orders of magnitude speedup for practical scenarios in dimension up to 100. Our solution is simpler and more efficient than competing methods.
Cite as

Tuyen Pham and Hubert Wagner. Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pham_et_al:LIPIcs.WADS.2025.45,
  author =	{Pham, Tuyen and Wagner, Hubert},
  title =	{{Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.45},
  URN =		{urn:nbn:de:0030-drops-242766},
  doi =		{10.4230/LIPIcs.WADS.2025.45},
  annote =	{Keywords: Kd-tree, k-d tree, nearest neighbour search, Bregman divergence, decomposable Bregman divergence, KL divergence, relative entropy, cross entropy, Shannon’s entropy}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.17
Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks

Authors: Mohimenul Kabir, Van-Giang Trinh, Samuel Pastva, and Kuldeep S Meel

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Boolean Networks (BNs) serve as a fundamental modeling framework for capturing complex dynamical systems across various domains, including systems biology, computational logic, and artificial intelligence. A crucial property of BNs is the presence of trap spaces - subspaces of the state space that, once entered, cannot be exited. Minimal trap spaces, in particular, play a significant role in analyzing the long-term behavior of BNs, making their efficient enumeration and counting essential. The fixed points in BNs are a special case of minimal trap spaces. In this work, we formulate several meaningful counting problems related to minimal trap spaces and fixed points in BNs. These problems provide valuable insights both within BN theory (e.g., in probabilistic reasoning and dynamical analysis) and in broader application areas, including systems biology, abstract argumentation, and logic programming. To address these computational challenges, we propose novel methods based on approximate answer set counting, leveraging techniques from answer set programming. Our approach efficiently approximates the number of minimal trap spaces and the number of fixed points without requiring exhaustive enumeration, making it particularly well-suited for large-scale BNs. Our experimental evaluation on an extensive and diverse set of benchmark instances shows that our methods significantly improve the feasibility of counting minimal trap spaces and fixed points, paving the way for new applications in BN analysis and beyond.
Cite as

Mohimenul Kabir, Van-Giang Trinh, Samuel Pastva, and Kuldeep S Meel. Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 17:1-17:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kabir_et_al:LIPIcs.CP.2025.17,
  author =	{Kabir, Mohimenul and Trinh, Van-Giang and Pastva, Samuel and Meel, Kuldeep S},
  title =	{{Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{17:1--17:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.17},
  URN =		{urn:nbn:de:0030-drops-238780},
  doi =		{10.4230/LIPIcs.CP.2025.17},
  annote =	{Keywords: Computational systems biology, Boolean network, Fixed point, Trap space, Answer set counting, Projected counting, Abstract argumentation, Logic programming}
}
Document
DOI: 10.4230/LIPIcs.SAND.2024.19
Complexity of Boolean Automata Networks Under Block-Parallel Update Modes

Authors: Kévin Perrot, Sylvain Sené, and Léah Tapin

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
Boolean automata networks (aka Boolean networks) are space-time discrete dynamical systems, studied as a model of computation and as a representative model of natural phenomena. A collection of simple entities (the automata) update their 0-1 states according to local rules. The dynamics of the network is highly sensitive to update modes, i.e., to the schedule according to which the automata apply their local rule. A new family of update modes appeared recently, called block-parallel, which is dual to the well studied block-sequential. Although basic, it embeds the rich feature of update repetitions among a temporal updating period, allowing for atypical asymptotic behaviors. In this paper, we prove that it is able to breed complex computations, squashing almost all decision problems on the dynamics to the traditionally highest (for reachability questions) class PSPACE. Despite obtaining these complexity bounds for a broad set of local and global properties, we also highlight a surprising gap: bijectivity is still coNP.
Cite as

Kévin Perrot, Sylvain Sené, and Léah Tapin. Complexity of Boolean Automata Networks Under Block-Parallel Update Modes. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{perrot_et_al:LIPIcs.SAND.2024.19,
  author =	{Perrot, K\'{e}vin and Sen\'{e}, Sylvain and Tapin, L\'{e}ah},
  title =	{{Complexity of Boolean Automata Networks Under Block-Parallel Update Modes}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.19},
  URN =		{urn:nbn:de:0030-drops-198973},
  doi =		{10.4230/LIPIcs.SAND.2024.19},
  annote =	{Keywords: Boolean networks, finite dynamical systems, block-parallel update schedule}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.AUTOMATA.2021
OASIcs, Volume 90, AUTOMATA 2021, Complete Volume

Authors: Alonso Castillo-Ramirez, Pierre Guillon, and Kévin Perrot

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
OASIcs, Volume 90, AUTOMATA 2021, Complete Volume
Cite as

27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 1-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{castilloramirez_et_al:OASIcs.AUTOMATA.2021,
  title =	{{OASIcs, Volume 90, AUTOMATA 2021, Complete Volume}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{1--186},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021},
  URN =		{urn:nbn:de:0030-drops-140087},
  doi =		{10.4230/OASIcs.AUTOMATA.2021},
  annote =	{Keywords: OASIcs, Volume 90, AUTOMATA 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.AUTOMATA.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Alonso Castillo-Ramirez, Pierre Guillon, and Kévin Perrot

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{castilloramirez_et_al:OASIcs.AUTOMATA.2021.0,
  author =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.0},
  URN =		{urn:nbn:de:0030-drops-140092},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.32
Rice-Like Theorems for Automata Networks

Authors: Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
We prove general complexity lower bounds on automata networks, in the style of Rice’s theorem, but in the computable world. Our main result is that testing any fixed first-order property on the dynamics of an automata network is either trivial, or NP-hard, or coNP-hard. Moreover, there exist such properties that are arbitrarily high in the polynomial-time hierarchy. We also prove that testing a first-order property given as input on an automata network (also part of the input) is PSPACE-hard. Besides, we show that, under a natural effectiveness condition, any nontrivial property of the limit set of a nondeterministic network is PSPACE-hard. We also show that it is PSPACE-hard to separate deterministic networks with a very high and a very low number of limit configurations; however, the problem of deciding whether the number of limit configurations is maximal up to a polynomial quantity belongs to the polynomial-time hierarchy.
Cite as

Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier. Rice-Like Theorems for Automata Networks. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gamard_et_al:LIPIcs.STACS.2021.32,
  author =	{Gamard, Guilhem and Guillon, Pierre and Perrot, Kevin and Theyssier, Guillaume},
  title =	{{Rice-Like Theorems for Automata Networks}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.32},
  URN =		{urn:nbn:de:0030-drops-136770},
  doi =		{10.4230/LIPIcs.STACS.2021.32},
  annote =	{Keywords: Automata networks, Rice theorem, complexity classes, polynomial hierarchy, hardness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.39
Balanced Connected Partitioning of Unweighted Grid Graphs

Authors: Cedric Berenger, Peter Niebert, and Kevin Perrot

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We consider a partitioning problem for grid graphs with special constraints: a (square) grid graph as well as a number of colors is given, a solution is a coloring approximatively assigning the same number of vertices to each color and such that the induced subgraph for each color is connected. In a "rooted" variant, a vertex to be included in the coloring for each color is specified as well. This problem has a concrete motivation in multimedia streaming applications. We show that the general problem is NP-complete. On the other hand, we define a reasonable easy subclass of grid graphs for which solutions always exist and can be computed by a greedy algorithm.
Cite as

Cedric Berenger, Peter Niebert, and Kevin Perrot. Balanced Connected Partitioning of Unweighted Grid Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{berenger_et_al:LIPIcs.MFCS.2018.39,
  author =	{Berenger, Cedric and Niebert, Peter and Perrot, Kevin},
  title =	{{Balanced Connected Partitioning of Unweighted Grid Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.39},
  URN =		{urn:nbn:de:0030-drops-96213},
  doi =		{10.4230/LIPIcs.MFCS.2018.39},
  annote =	{Keywords: grid graphs, connected partitioning, NP-completeness, graph algorithm}
}
  • Refine by Type
  • 7 Document/PDF
  • 2 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 4 2021
  • 1 2018

  • Refine by Author
  • 3 Guillon, Pierre
  • 3 Perrot, Kévin
  • 2 Castillo-Ramirez, Alonso
  • 2 Perrot, Kevin
  • 1 Berenger, Cedric
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 3 Theory of computation → Models of computation
  • 2 Computing methodologies
  • 2 Mathematics of computing
  • 1 Applied computing → Systems biology
  • 1 Computing methodologies → Logic programming and answer set programming
  • Show More...

  • Refine by Keyword
  • 1 Abstract argumentation
  • 1 Answer set counting
  • 1 Automata networks
  • 1 Boolean network
  • 1 Boolean networks
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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