Search Results

Documents authored by Grandjean, Anaël

Found 2 Possible Name Variants:

Grandjean, Anaël

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.ICALP.2016.115
A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods

Authors: Anaël Grandjean and Victor Poupet

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all twodimensional languages recognized by cellular automata working on complete neighborhoods.
Cite as

Anaël Grandjean and Victor Poupet. A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 115:1-115:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.ICALP.2016.115,
  author =	{Grandjean, Ana\"{e}l and Poupet, Victor},
  title =	{{A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{115:1--115:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.115},
  URN =		{urn:nbn:de:0030-drops-62502},
  doi =		{10.4230/LIPIcs.ICALP.2016.115},
  annote =	{Keywords: 2D Cellular automata, linear acceleration, language recognition}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.367
Comparing 1D and 2D Real Time on Cellular Automata

Authors: Anaël Grandjean and Victor Poupet

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

Abstract
We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood. We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.
Cite as

Anaël Grandjean and Victor Poupet. Comparing 1D and 2D Real Time on Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 367-378, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.STACS.2015.367,
  author =	{Grandjean, Ana\"{e}l and Poupet, Victor},
  title =	{{Comparing 1D and 2D Real Time on Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{367--378},
  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.367},
  URN =		{urn:nbn:de:0030-drops-49275},
  doi =		{10.4230/LIPIcs.STACS.2015.367},
  annote =	{Keywords: Cellular automata, real time, language recognition}
}

Grandjean, Anael

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.ICALP.2016.115
A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods

Authors: Anaël Grandjean and Victor Poupet

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all twodimensional languages recognized by cellular automata working on complete neighborhoods.
Cite as

Anaël Grandjean and Victor Poupet. A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 115:1-115:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.ICALP.2016.115,
  author =	{Grandjean, Ana\"{e}l and Poupet, Victor},
  title =	{{A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{115:1--115:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.115},
  URN =		{urn:nbn:de:0030-drops-62502},
  doi =		{10.4230/LIPIcs.ICALP.2016.115},
  annote =	{Keywords: 2D Cellular automata, linear acceleration, language recognition}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.367
Comparing 1D and 2D Real Time on Cellular Automata

Authors: Anaël Grandjean and Victor Poupet

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

Abstract
We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood. We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.
Cite as

Anaël Grandjean and Victor Poupet. Comparing 1D and 2D Real Time on Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 367-378, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{grandjean_et_al:LIPIcs.STACS.2015.367,
  author =	{Grandjean, Ana\"{e}l and Poupet, Victor},
  title =	{{Comparing 1D and 2D Real Time on Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{367--378},
  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.367},
  URN =		{urn:nbn:de:0030-drops-49275},
  doi =		{10.4230/LIPIcs.STACS.2015.367},
  annote =	{Keywords: Cellular automata, real time, language recognition}
}
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