Search Results

Documents authored by Callard, Antonin

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.STACS.2020.8
Descriptive Complexity on Non-Polish Spaces

Authors: Antonin Callard and Mathieu Hoyrup

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Represented spaces are the spaces on which computations can be performed. We investigate the descriptive complexity of sets in represented spaces. We prove that the standard representation of a countably-based space preserves the effective descriptive complexity of sets. We prove that some results from descriptive set theory on Polish spaces extend to arbitrary countably-based spaces. We study the larger class of coPolish spaces, showing that their representation does not always preserve the complexity of sets, and we relate this mismatch with the sequential aspects of the space. We study in particular the space of polynomials.
Cite as

Antonin Callard and Mathieu Hoyrup. Descriptive Complexity on Non-Polish Spaces. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{callard_et_al:LIPIcs.STACS.2020.8,
  author =	{Callard, Antonin and Hoyrup, Mathieu},
  title =	{{Descriptive Complexity on Non-Polish Spaces}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.8},
  URN =		{urn:nbn:de:0030-drops-118694},
  doi =		{10.4230/LIPIcs.STACS.2020.8},
  annote =	{Keywords: Represented space, Computable analysis, Descriptive set theory, CoPolish spaces}
}
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