24 Search Results for "Guillon, Pierre"

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.STACS.2026.63
Generalised Quantifiers Based on Rabin-Mostowski Index

Authors: Denis Kuperberg, Damian Niwiński, Paweł Parys, and Michał Skrzypczak

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In this work we introduce new generalised quantifiers which allow us to express the Rabin-Mostowski index of automata. Our main results study expressive power and decidability of the monadic second-order (MSO) logic extended with these quantifiers. We study these problems in the realm of both ω-words and infinite trees. As it turns out, the pictures in these two cases are very different. In the case of ω-words the new quantifiers can be effectively expressed in pure MSO logic. In contrast, in the case of infinite trees, addition of these quantifiers leads to an undecidable formalism. To realise index-quantifier elimination, we consider the extension of MSO by game quantifiers. As a tool, we provide a specific quantifier-elimination procedure for them. Moreover, we introduce a novel construction of transducers realising strategies in ω-regular games with monadic parameters.
Cite as

Denis Kuperberg, Damian Niwiński, Paweł Parys, and Michał Skrzypczak. Generalised Quantifiers Based on Rabin-Mostowski Index. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 63:1-63:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kuperberg_et_al:LIPIcs.STACS.2026.63,
  author =	{Kuperberg, Denis and Niwi\'{n}ski, Damian and Parys, Pawe{\l} and Skrzypczak, Micha{\l}},
  title =	{{Generalised Quantifiers Based on Rabin-Mostowski Index}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{63:1--63:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.63},
  URN =		{urn:nbn:de:0030-drops-255526},
  doi =		{10.4230/LIPIcs.STACS.2026.63},
  annote =	{Keywords: monadic quantifiers, decidability, quantifier elimination, parity automata, game quantifier, Rabin-Mostowski index}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.139
Minimality and Computability of Languages of G-Shifts

Authors: Djamel Eddine Amir and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for G-shifts, where G is a finitely generated group with decidable word problem. A G-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of G-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.
Cite as

Djamel Eddine Amir and Benjamin Hellouin de Menibus. Minimality and Computability of Languages of G-Shifts. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 139:1-139:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.ICALP.2025.139,
  author =	{Amir, Djamel Eddine and Hellouin de Menibus, Benjamin},
  title =	{{Minimality and Computability of Languages of G-Shifts}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{139:1--139:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.139},
  URN =		{urn:nbn:de:0030-drops-235161},
  doi =		{10.4230/LIPIcs.ICALP.2025.139},
  annote =	{Keywords: shifts, subshifts, minimal shifts, computable language, computability, strong computable type, descriptive complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.21
Computability of Extender Sets in Multidimensional Subshifts

Authors: Antonin Callard, Léo Paviet Salomon, and Pascal Vanier

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Subshifts are sets of colorings of ℤ^d defined by families of forbidden patterns. Given a subshift and a finite pattern, its extender set is the set of admissible completions of this pattern. It has been conjectured that the behavior of extender sets, and in particular their growth called extender entropy [French and Pavlov, 2019], could provide a way to separate the classes of sofic and effective subshifts. We prove here that both classes have the same possible extender entropies: exactly the Π₃ real numbers of [0,+∞).
Cite as

Antonin Callard, Léo Paviet Salomon, and Pascal Vanier. Computability of Extender Sets in Multidimensional Subshifts. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.STACS.2025.21,
  author =	{Callard, Antonin and Paviet Salomon, L\'{e}o and Vanier, Pascal},
  title =	{{Computability of Extender Sets in Multidimensional Subshifts}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.21},
  URN =		{urn:nbn:de:0030-drops-228462},
  doi =		{10.4230/LIPIcs.STACS.2025.21},
  annote =	{Keywords: Symbolic dynamics, subshifts, extender sets, extender entropy, computability, sofic shifts, tilings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.48
Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata

Authors: Benjamin Hellouin de Menibus and Pacôme Perrotin

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of 4-way finite automata for two-dimensional finite words. We extend the model to allow for nondeterminism and alternation of quantifiers. We prove that the recognised subshifts form a strict subclass of sofic subshifts, and that the classes corresponding to existential and universal nondeterminism are incomparable and both larger that the deterministic class. We define a hierarchy of subshifts recognised by plane-walking automata with alternating quantifiers, which we conjecture to be strict.
Cite as

Benjamin Hellouin de Menibus and Pacôme Perrotin. Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hellouindemenibus_et_al:LIPIcs.STACS.2025.48,
  author =	{Hellouin de Menibus, Benjamin and Perrotin, Pac\^{o}me},
  title =	{{Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.48},
  URN =		{urn:nbn:de:0030-drops-228540},
  doi =		{10.4230/LIPIcs.STACS.2025.48},
  annote =	{Keywords: Formal languages, Finite automata, Subshifts, Symbolic dynamics, Tilings}
}
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
Invited Talk
DOI: 10.4230/OASIcs.AUTOMATA.2021.1
Dynamical Properties of Disjunctive Boolean Networks (Invited Talk)

Authors: Maximilien Gadouleau

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

Abstract
A Boolean network is a mapping f :{0,1}ⁿ → {0,1}ⁿ, which can be used to model networks of n interacting entities, each having a local Boolean state that evolves over time according to a deterministic function of the current configuration of states. In this paper, we are interested in disjunctive networks, where each local function is simply the disjunction of a set of variables. As such, this network is somewhat homogeneous, though the number of variables may vary from entity to entity, thus yielding a generalised cellular automaton. The aim of this paper is to review some of the main results, derive some additional fundamental results, and highlight some open problems on the dynamics of disjunctive networks. We first review the different defining characteristics of disjunctive networks and several ways of representing them using graphs, Boolean matrices, or binary relations. We then focus on three dynamical properties of disjunctive networks: their image points, their periodic points, and their fixed points. For each class of points, we review how they can be characterised and study how many they could be. The paper finishes with different avenues for future work on the dynamics of disjunctive networks and how to generalise them.
Cite as

Maximilien Gadouleau. Dynamical Properties of Disjunctive Boolean Networks (Invited Talk). In 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:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gadouleau:OASIcs.AUTOMATA.2021.1,
  author =	{Gadouleau, Maximilien},
  title =	{{Dynamical Properties of Disjunctive Boolean Networks}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{1:1--1:15},
  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.1},
  URN =		{urn:nbn:de:0030-drops-140105},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.1},
  annote =	{Keywords: Boolean networks, disjunction, conjunction, fixed points, rank}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.AUTOMATA.2021.2
Regular Languages: To Finite Automata and Beyond (Invited Talk)

Authors: Luca Prigioniero

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

Abstract
It is well known that the class of regular languages coincides with the class of languages recognized by finite automata. Nevertheless, many other characterizations of this class in terms of computational devices and generative models are present in the literature. For example, by suitably restricting more powerful models such as context-free grammars, pushdown automata, and Turing machines, it is possible to obtain formal models that generate or recognize regular languages only. These restricted formalisms provide alternative representations of regular languages that may be significantly more concise than other models that share the same expressive power. The goal of this work is to provide an overview of old and recent results on these formal systems from a descriptional complexity perspective, that is by considering the relationships between the sizes of such devices. We also present some results related to the investigation of the famous question posed by Sakoda and Sipser in 1978, concerning the size blowups from nondeterministic finite automata to two-way deterministic finite automata.
Cite as

Luca Prigioniero. Regular Languages: To Finite Automata and Beyond (Invited Talk). In 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. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{prigioniero:OASIcs.AUTOMATA.2021.2,
  author =	{Prigioniero, Luca},
  title =	{{Regular Languages: To Finite Automata and Beyond}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{2:1--2:16},
  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.2},
  URN =		{urn:nbn:de:0030-drops-140115},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.2},
  annote =	{Keywords: Regular languages, descriptional complexity, finite automata}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.AUTOMATA.2021.3
Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything (Invited Talk)

Authors: Siamak Taati

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

Abstract
We consider reversible and surjective cellular automata perturbed with noise. We show that, in the presence of positive additive noise, the cellular automaton forgets all the information regarding its initial configuration exponentially fast. In particular, the state of a finite collection of cells with diameter n becomes indistinguishable from pure noise after O(log n) time steps. This highlights the seemingly unavoidable need for irreversibility in order to perform scalable reliable computation in the presence of noise.
Cite as

Siamak Taati. Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything (Invited Talk). In 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. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{taati:OASIcs.AUTOMATA.2021.3,
  author =	{Taati, Siamak},
  title =	{{Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{3:1--3:15},
  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.3},
  URN =		{urn:nbn:de:0030-drops-140128},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.3},
  annote =	{Keywords: Reversible cellular automata, surjective cellular automata, noise, probabilistic cellular automata, ergodicity, entropy, reversible computing, reliable computing, fault tolerance}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.AUTOMATA.2021.4
Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk)

Authors: Ilkka Törmä

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

Abstract
The fixed point construction is a method for designing tile sets and cellular automata with highly nontrivial dynamical and computational properties. It produces an infinite hierarchy of systems where each layer simulates the next one. The simulations are implemented entirely by computations of Turing machines embedded in the tilings or spacetime diagrams. We present an overview of the construction and list its applications in the literature.
Cite as

Ilkka Törmä. Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk). In 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. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{torma:OASIcs.AUTOMATA.2021.4,
  author =	{T\"{o}rm\"{a}, Ilkka},
  title =	{{Fixed Point Constructions in Tilings and Cellular Automata}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{4:1--4:13},
  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.4},
  URN =		{urn:nbn:de:0030-drops-140135},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.4},
  annote =	{Keywords: Tilings, Wang tiles, cellular automata, multidimensional symbolic dynamics, self-simulation}
}
Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.5
Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets

Authors: Laurent David, Colin Defant, Michael Joseph, Matthew Macauley, and Alex McDonough

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

Abstract
Though iterated maps and dynamical systems are not new to combinatorics, they have enjoyed a renewed prominence over the past decade through the elevation of the subfield that has become known as dynamical algebraic combinatorics. Some of the problems that have gained popularity can also be cast and analyzed as finite asynchronous cellular automata (CA). However, these two fields are fairly separate, and while there are some individuals who work in both, that is the exception rather than the norm. In this article, we will describe our ongoing work on toggling independent sets on graphs. This will be preceded by an overview of how this project arose from new combinatorial problems involving homomesy, toggling, and resonance. Though the techniques that we explore are directly applicable to ECA rule 1, many of them can be generalized to other cellular automata. Moreover, some of the ideas that we borrow from cellular automata can be adapted to problems in dynamical algebraic combinatorics. It is our hope that this article will inspire new problems in both fields and connections between them.
Cite as

Laurent David, Colin Defant, Michael Joseph, Matthew Macauley, and Alex McDonough. Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets. In 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. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{david_et_al:OASIcs.AUTOMATA.2021.5,
  author =	{David, Laurent and Defant, Colin and Joseph, Michael and Macauley, Matthew and McDonough, Alex},
  title =	{{Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{5:1--5:16},
  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.5},
  URN =		{urn:nbn:de:0030-drops-140145},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.5},
  annote =	{Keywords: Asynchronous cellular automata, Covering space, Coxeter element, Dynamical algebraic combinatorics, Group action, Homomesy, Independent set, Resonance, Toggling, Toric equivalence}
}
Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.6
Rice’s Theorem for Generic Limit Sets of Cellular Automata

Authors: Martin Delacourt

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

Abstract
The generic limit set of a cellular automaton is a topologically defined set of configurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was defined by Milnor then studied by Djenaoui and Guillon first, and by Törmä later. They gave properties of this set related to the dynamics of the cellular automaton, and the maximal complexity of its language. In this paper, we prove that every non trivial property of these generic limit sets of cellular automata is undecidable.
Cite as

Martin Delacourt. Rice’s Theorem for Generic Limit Sets of Cellular Automata. In 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. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{delacourt:OASIcs.AUTOMATA.2021.6,
  author =	{Delacourt, Martin},
  title =	{{Rice’s Theorem for Generic Limit Sets of Cellular Automata}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{6:1--6:12},
  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.6},
  URN =		{urn:nbn:de:0030-drops-140151},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.6},
  annote =	{Keywords: cellular automata, dynamical systems, generic-limit sets, Rice’s theorem, subshifts}
}
Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.7
Cellular Automata and Kan Extensions

Authors: Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher

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

Abstract
In this paper, we formalize precisely the sense in which the application of a cellular automaton to partial configurations is a natural extension of its local transition function through the categorical notion of Kan extension. In fact, the two possible ways to do such an extension and the ingredients involved in their definition are related through Kan extensions in many ways. These relations provide additional links between computer science and category theory, and also give a new point of view on the famous Curtis-Hedlund theorem of cellular automata from the extended topological point of view provided by category theory. These links also allow to relatively easily generalize concepts pioneered by cellular automata to arbitrary kinds of possibly evolving spaces. No prior knowledge of category theory is assumed.
Cite as

Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Cellular Automata and Kan Extensions. In 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. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fernandez_et_al:OASIcs.AUTOMATA.2021.7,
  author =	{Fernandez, Alexandre and Maignan, Luidnel and Spicher, Antoine},
  title =	{{Cellular Automata and Kan Extensions}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{7:1--7:12},
  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.7},
  URN =		{urn:nbn:de:0030-drops-140160},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.7},
  annote =	{Keywords: Cellular Automata, Kan Extension, Category Theory, Global Transformation}
}
Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.8
Conjunctive Grammars, Cellular Automata and Logic

Authors: Théo Grente and Étienne Grandjean

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

Abstract
The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognized by real-time one-dimensional one-way cellular automata. We prove two weakened versions of the open question Conj ⊆? RealTime1CA, where RealTime1CA is the class of languages recognized by real-time one-dimensional two-way cellular automata: 1) it is true for unary languages; 2) Conj ⊆ RealTime2OCA, i.e. any conjunctive language is recognized by a real-time two-dimensional one-way cellular automaton. Interestingly, we express the rules of a conjunctive grammar in two Horn logics, which exactly characterize the complexity classes RealTime1CA and RealTime2OCA.
Cite as

Théo Grente and Étienne Grandjean. Conjunctive Grammars, Cellular Automata and Logic. In 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. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grente_et_al:OASIcs.AUTOMATA.2021.8,
  author =	{Grente, Th\'{e}o and Grandjean, \'{E}tienne},
  title =	{{Conjunctive Grammars, Cellular Automata and Logic}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-140170},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.8},
  annote =	{Keywords: Computational complexity, Real-time, One-dimensional/two-dimensional cellular automaton, One-way/two-way communication, Grid-circuit, Unary language, Descriptive complexity, Existential second-order logic, Horn formula}
}
  • Refine by Type
  • 23 Document/PDF
  • 4 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 16 2021
  • 1 2019
  • 1 2017
  • Show More...

  • Refine by Author
  • 6 Guillon, Pierre
  • 2 Castillo-Ramirez, Alonso
  • 2 Hellouin de Menibus, Benjamin
  • 2 Perrot, Kévin
  • 1 Amir, Djamel Eddine
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs
  • 14 OASIcs

  • Refine by Classification
  • 9 Theory of computation → Models of computation
  • 3 Mathematics of computing → Discrete mathematics
  • 3 Theory of computation → Automata over infinite objects
  • 2 Computing methodologies
  • 2 Mathematics of computing
  • Show More...

  • Refine by Keyword
  • 4 cellular automata
  • 3 subshifts
  • 2 Symbolic dynamics
  • 2 Tilings
  • 2 computability
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact