Search Results

Documents authored by Bacquey, Nicolas

Document
DOI: 10.4230/LIPIcs.ICALP.2017.99
Definability by Horn Formulas and Linear Time on Cellular Automata

Authors: Nicolas Bacquey, Etienne Grandjean, and Frédéric Olive

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We establish an exact logical characterization of linear time complexity of cellular automata of dimension d, for any fixed d: a set of pictures of dimension d belongs to this complexity class iff it is definable in existential second-order logic restricted to monotonic Horn formulas with built-in successor function and d+1 first-order variables. This logical characterization is optimal modulo an open problem in parallel complexity. Furthermore, its proof provides a systematic method for transforming an inductive formula defining some problem into a cellular automaton that computes it in linear time.
Cite as

Nicolas Bacquey, Etienne Grandjean, and Frédéric Olive. Definability by Horn Formulas and Linear Time on Cellular Automata. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 99:1-99:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bacquey_et_al:LIPIcs.ICALP.2017.99,
  author =	{Bacquey, Nicolas and Grandjean, Etienne and Olive, Fr\'{e}d\'{e}ric},
  title =	{{Definability by Horn Formulas and Linear Time on Cellular Automata}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{99:1--99:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.99},
  URN =		{urn:nbn:de:0030-drops-74174},
  doi =		{10.4230/LIPIcs.ICALP.2017.99},
  annote =	{Keywords: picture languages, linear time, cellular automata of any dimension, local induction, descriptive complexity, second-order logic, horn formulas, logic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.112
Complexity classes on spatially periodic Cellular Automata

Authors: Nicolas Bacquey

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
This article deals with cellular automata (CA) working over periodic configurations, as opposed to standard CA, where the initial configuration is bounded by persistent symbols. We study the capabilities of language recognition and computation of functions over such automata, as well as the complexity classes they define over languages and functions. We show that these new complexity classes coincide with the standard ones starting from polynomial time. As a by-product, we present a CA that solves a somehow relaxed version of the density classification problem.
Cite as

Nicolas Bacquey. Complexity classes on spatially periodic Cellular Automata. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 112-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bacquey:LIPIcs.STACS.2014.112,
  author =	{Bacquey, Nicolas},
  title =	{{Complexity classes on spatially periodic Cellular Automata}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{112--124},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.112},
  URN =		{urn:nbn:de:0030-drops-44519},
  doi =		{10.4230/LIPIcs.STACS.2014.112},
  annote =	{Keywords: Language recognition, cyclic languages, computable functions, algorithms on Cellular Automata, linear space, polynomial time, density classification p}
}
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