Search Results

Documents authored by Vanier, Pascal

Document
DOI: 10.4230/LIPIcs.MFCS.2023.75
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}
}
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.2019.40
A Characterization of Subshifts with Computable Language

Authors: Emmanuel Jeandel and Pascal Vanier

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Subshifts are sets of colorings of Z^d by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by the first author. In particular we prove several theorems on subshifts inspired by Higman’s embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type.
Cite as

Emmanuel Jeandel and Pascal Vanier. A Characterization of Subshifts with Computable Language. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.STACS.2019.40,
  author =	{Jeandel, Emmanuel and Vanier, Pascal},
  title =	{{A Characterization of Subshifts with Computable Language}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.40},
  URN =		{urn:nbn:de:0030-drops-102798},
  doi =		{10.4230/LIPIcs.STACS.2019.40},
  annote =	{Keywords: subshifts, computability, Enumeration degree, Turing degree, minimal subshifts}
}
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.2013.490
Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type

Authors: Emmanuel Jeandel and Pascal Vanier

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts of finite type (SFTs) in dimension d > 1. In particular, we prove that the factorization problem is Sigma^0_3-complete and that the conjugacy and embedding problems are Sigma^0_1-complete in the arithmetical hierarchy.
Cite as

Emmanuel Jeandel and Pascal Vanier. Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 490-501, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.STACS.2013.490,
  author =	{Jeandel, Emmanuel and Vanier, Pascal},
  title =	{{Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{490--501},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.490},
  URN =		{urn:nbn:de:0030-drops-39592},
  doi =		{10.4230/LIPIcs.STACS.2013.490},
  annote =	{Keywords: Subshifts, Computability, Factorization, Embedding, Conjugacy}
}
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 About DROPS Imprint Privacy Contact