4 Search Results for "Hellouin de Menibus, Benjamin"

Document
DOI: 10.4230/LIPIcs.STACS.2022.19
The Aperiodic Domino Problem in Higher Dimension

Authors: Antonin Callard and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. [Grandjean et al., 2018] proved that this problem is co-recursively enumerable (Π₀¹-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic (Σ₁¹-complete), in higher dimension: d ≥ 4 in the finite type case, d ≥ 3 for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large.
Cite as

Antonin Callard and Benjamin Hellouin de Menibus. The Aperiodic Domino Problem in Higher Dimension. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 19:1-19:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.STACS.2022.19,
  author =	{Callard, Antonin and Hellouin de Menibus, Benjamin},
  title =	{{The Aperiodic Domino Problem in Higher Dimension}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra 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.2022.19},
  URN =		{urn:nbn:de:0030-drops-158296},
  doi =		{10.4230/LIPIcs.STACS.2022.19},
  annote =	{Keywords: Subshift, periodicity, aperiodicity, domino problem, subshift of finite type, sofic subshift, effective subshift, tilings, computability}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.122
Computational Characterization of Surface Entropies for ℤ² Subshifts of Finite Type

Authors: Antonin Callard and Pascal Vanier

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Subshifts of finite type (SFTs) are sets of colorings of the plane that avoid a finite family of forbidden patterns. In this article, we are interested in the behavior of the growth of the number of valid patterns in SFTs. While entropy h corresponds to growths that are squared exponential 2^{hn²}, surface entropy (introduced in Pace’s thesis in 2018) corresponds to the eventual linear term in exponential growths. We give here a characterization of the possible surface entropies of SFTs as the Π₃ real numbers of [0,+∞].
Cite as

Antonin Callard and Pascal Vanier. Computational Characterization of Surface Entropies for ℤ² Subshifts of Finite Type. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 122:1-122:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.ICALP.2021.122,
  author =	{Callard, Antonin and Vanier, Pascal},
  title =	{{Computational Characterization of Surface Entropies for \mathbb{Z}² Subshifts of Finite Type}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{122:1--122:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.122},
  URN =		{urn:nbn:de:0030-drops-141914},
  doi =		{10.4230/LIPIcs.ICALP.2021.122},
  annote =	{Keywords: surface entropy, arithmetical hierarchy of real numbers, 2D subshifts, symbolic dynamics}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.128
Aperiodic Points in Z²-subshifts

Authors: Anael Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the structure of aperiodic points in Z^2-subshifts, and in particular the positions at which they fail to be periodic. We prove that if a Z^2-subshift contains points whose smallest period is arbitrarily large, then it contains an aperiodic point. This lets us characterise the computational difficulty of deciding if an Z^2-subshift of finite type contains an aperiodic point. Another consequence is that Z^2-subshifts with no aperiodic point have a very strong dynamical structure and are almost topologically conjugate to some Z-subshift. Finally, we use this result to characterize sets of possible slopes of periodicity for Z^3-subshifts of finite type.
Cite as

Anael Grandjean, Benjamin Hellouin de Menibus, and Pascal Vanier. Aperiodic Points in Z²-subshifts. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 128:1-128:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.ICALP.2018.128,
  author =	{Grandjean, Anael and Hellouin de Menibus, Benjamin and Vanier, Pascal},
  title =	{{Aperiodic Points in Z²-subshifts}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{128:1--128:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.128},
  URN =		{urn:nbn:de:0030-drops-91323},
  doi =		{10.4230/LIPIcs.ICALP.2018.128},
  annote =	{Keywords: Subshifts of finite type, Wang tiles, periodicity, aperiodicity, computability, tilings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.262
Construction of mu-Limit Sets of Two-dimensional Cellular Automata

Authors: Martin Delacourt and Benjamin Hellouin de Ménibus

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We prove a characterisation of \mu-limit sets of two-dimensional cellular automata, extending existing results in the one-dimensional case. This sets describe the typical asymptotic behaviour of the cellular automaton, getting rid of exceptional cases, when starting from the uniform measure.
Cite as

Martin Delacourt and Benjamin Hellouin de Ménibus. Construction of mu-Limit Sets of Two-dimensional Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 262-274, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{delacourt_et_al:LIPIcs.STACS.2015.262,
  author =	{Delacourt, Martin and Hellouin de M\'{e}nibus, Benjamin},
  title =	{{Construction of mu-Limit Sets of Two-dimensional Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{262--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.262},
  URN =		{urn:nbn:de:0030-drops-49197},
  doi =		{10.4230/LIPIcs.STACS.2015.262},
  annote =	{Keywords: cellular automata, dynamical systems, mu-limit sets, subshifts, measures}
}
  • Refine by Author
  • 2 Callard, Antonin
  • 2 Hellouin de Menibus, Benjamin
  • 2 Vanier, Pascal
  • 1 Delacourt, Martin
  • 1 Grandjean, Anael
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Models of computation
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 aperiodicity
  • 2 computability
  • 2 periodicity
  • 2 tilings
  • 1 2D subshifts
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2015
  • 1 2018
  • 1 2021
  • 1 2022

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact