Search Results

Documents authored by Richard, Gaetan

Found 2 Possible Name Variants:

Richard, Gaétan

Document
DOI: 10.4230/LIPIcs.STACS.2017.54
On the Synchronisation Problem over Cellular Automata

Authors: Gaétan Richard

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Cellular automata are a discrete, synchronous, and uniform dynamical system that give rise to a wide range of dynamical behaviours. In this paper, we investigate whether this system can achieve synchronisation. We study the cases of classical bi-infinite configurations, periodic configurations, and periodic configurations of prime period. In the two former cases, we prove that only a "degenerated" form of synchronisation - there exists a fix-point - is possible. In the latter case, we give an explicit construction of a cellular automaton for which any periodic configuration of prime period eventually converges to cycle of two uniform configurations. Our construction is based upon sophisticated tools: aperiodic NW-deterministic tilings and partitioned intervals.
Cite as

Gaétan Richard. On the Synchronisation Problem over Cellular Automata. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{richard:LIPIcs.STACS.2017.54,
  author =	{Richard, Ga\'{e}tan},
  title =	{{On the Synchronisation Problem over Cellular Automata}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.54},
  URN =		{urn:nbn:de:0030-drops-69780},
  doi =		{10.4230/LIPIcs.STACS.2017.54},
  annote =	{Keywords: cellular automata, dynamical systems, aperiodic tiling, synchronisation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.273
A speed-up of oblivious multi-head finite automata by cellular automata

Authors: Alex Borelllo, Gaetan Richard, and Veronique Terrier

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
In this paper, we present a parallel speed-up of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head finite automata and is characterized by the fact that the trajectory of the heads only depends on the length of the input word. While the original $k$-head finite automaton works in time $O(n^k)$, its corresponding cellular automaton performs the same task in time $O(n^(k-1)log(n))$ and space $O(n^(k - 1))$.
Cite as

Alex Borelllo, Gaetan Richard, and Veronique Terrier. A speed-up of oblivious multi-head finite automata by cellular automata. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 273-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{borelllo_et_al:LIPIcs.STACS.2011.273,
  author =	{Borelllo, Alex and Richard, Gaetan and Terrier, Veronique},
  title =	{{A speed-up of oblivious multi-head finite automata by cellular automata}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{273--283},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.273},
  URN =		{urn:nbn:de:0030-drops-30172},
  doi =		{10.4230/LIPIcs.STACS.2011.273},
  annote =	{Keywords: oblivious multi-head finite automata, cellular automata, parallel speed-up, simulation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2474
Revisiting the Rice Theorem of Cellular Automata

Authors: Pierre Guillon and Gaétan Richard

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
A cellular automaton is a parallel synchronous computing model, which consists in a juxtaposition of finite automata whose state evolves according to that of their neighbors. It induces a dynamical system on the set of configurations, \ie the infinite sequences of cell states. The limit set of the cellular automaton is the set of configurations which can be reached arbitrarily late in the evolution. In this paper, we prove that all properties of limit sets of cellular automata with binary-state cells are undecidable, except surjectivity. This is a refinement of the classical ``Rice Theorem'' that Kari proved on cellular automata with arbitrary state sets.
Cite as

Pierre Guillon and Gaétan Richard. Revisiting the Rice Theorem of Cellular Automata. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 441-452, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{guillon_et_al:LIPIcs.STACS.2010.2474,
  author =	{Guillon, Pierre and Richard, Ga\'{e}tan},
  title =	{{Revisiting the Rice Theorem of Cellular Automata}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{441--452},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2474},
  URN =		{urn:nbn:de:0030-drops-24744},
  doi =		{10.4230/LIPIcs.STACS.2010.2474},
  annote =	{Keywords: Cellular automata, undecidability}
}

Richard, Gaetan

Document
DOI: 10.4230/LIPIcs.STACS.2017.54
On the Synchronisation Problem over Cellular Automata

Authors: Gaétan Richard

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Cellular automata are a discrete, synchronous, and uniform dynamical system that give rise to a wide range of dynamical behaviours. In this paper, we investigate whether this system can achieve synchronisation. We study the cases of classical bi-infinite configurations, periodic configurations, and periodic configurations of prime period. In the two former cases, we prove that only a "degenerated" form of synchronisation - there exists a fix-point - is possible. In the latter case, we give an explicit construction of a cellular automaton for which any periodic configuration of prime period eventually converges to cycle of two uniform configurations. Our construction is based upon sophisticated tools: aperiodic NW-deterministic tilings and partitioned intervals.
Cite as

Gaétan Richard. On the Synchronisation Problem over Cellular Automata. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{richard:LIPIcs.STACS.2017.54,
  author =	{Richard, Ga\'{e}tan},
  title =	{{On the Synchronisation Problem over Cellular Automata}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.54},
  URN =		{urn:nbn:de:0030-drops-69780},
  doi =		{10.4230/LIPIcs.STACS.2017.54},
  annote =	{Keywords: cellular automata, dynamical systems, aperiodic tiling, synchronisation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.273
A speed-up of oblivious multi-head finite automata by cellular automata

Authors: Alex Borelllo, Gaetan Richard, and Veronique Terrier

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
In this paper, we present a parallel speed-up of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head finite automata and is characterized by the fact that the trajectory of the heads only depends on the length of the input word. While the original $k$-head finite automaton works in time $O(n^k)$, its corresponding cellular automaton performs the same task in time $O(n^(k-1)log(n))$ and space $O(n^(k - 1))$.
Cite as

Alex Borelllo, Gaetan Richard, and Veronique Terrier. A speed-up of oblivious multi-head finite automata by cellular automata. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 273-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{borelllo_et_al:LIPIcs.STACS.2011.273,
  author =	{Borelllo, Alex and Richard, Gaetan and Terrier, Veronique},
  title =	{{A speed-up of oblivious multi-head finite automata by cellular automata}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{273--283},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.273},
  URN =		{urn:nbn:de:0030-drops-30172},
  doi =		{10.4230/LIPIcs.STACS.2011.273},
  annote =	{Keywords: oblivious multi-head finite automata, cellular automata, parallel speed-up, simulation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2474
Revisiting the Rice Theorem of Cellular Automata

Authors: Pierre Guillon and Gaétan Richard

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
A cellular automaton is a parallel synchronous computing model, which consists in a juxtaposition of finite automata whose state evolves according to that of their neighbors. It induces a dynamical system on the set of configurations, \ie the infinite sequences of cell states. The limit set of the cellular automaton is the set of configurations which can be reached arbitrarily late in the evolution. In this paper, we prove that all properties of limit sets of cellular automata with binary-state cells are undecidable, except surjectivity. This is a refinement of the classical ``Rice Theorem'' that Kari proved on cellular automata with arbitrary state sets.
Cite as

Pierre Guillon and Gaétan Richard. Revisiting the Rice Theorem of Cellular Automata. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 441-452, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{guillon_et_al:LIPIcs.STACS.2010.2474,
  author =	{Guillon, Pierre and Richard, Ga\'{e}tan},
  title =	{{Revisiting the Rice Theorem of Cellular Automata}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{441--452},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2474},
  URN =		{urn:nbn:de:0030-drops-24744},
  doi =		{10.4230/LIPIcs.STACS.2010.2474},
  annote =	{Keywords: Cellular automata, undecidability}
}
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