Search Results

Documents authored by Perrot, Kévin

Found 2 Possible Name Variants:

Perrot, Kévin

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}
}

Perrot, Kevin

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}
}
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