Search Results

Documents authored by Paviet Salomon, Léo


Document
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
Realizing Finitely Presented Groups as Projective Fundamental Groups of SFTs

Authors: Léo Paviet Salomon and Pascal Vanier

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
Subshifts are sets of colourings - or tilings - of the plane, defined by local constraints. Historically introduced as discretizations of continuous dynamical systems, they are also heavily related to computability theory. In this article, we study a conjugacy invariant for subshifts, known as the projective fundamental group. It is defined via paths inside and between configurations. We show that any finitely presented group can be realized as a projective fundamental group of some SFT.

Cite as

Léo Paviet Salomon and Pascal Vanier. Realizing Finitely Presented Groups as Projective Fundamental Groups of SFTs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{pavietsalomon_et_al:LIPIcs.MFCS.2023.75,
  author =	{Paviet Salomon, L\'{e}o and Vanier, Pascal},
  title =	{{Realizing Finitely Presented Groups as Projective Fundamental Groups of SFTs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{75:1--75:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.75},
  URN =		{urn:nbn:de:0030-drops-186098},
  doi =		{10.4230/LIPIcs.MFCS.2023.75},
  annote =	{Keywords: Subshifts, Wang tiles, Dynamical Systems, Computability, Subshift of Finite Type, Fundamental Group}
}
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