License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.99
URN: urn:nbn:de:0030-drops-74174
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7417/
Bacquey, Nicolas ;
Grandjean, Etienne ;
Olive, Frédéric
Definability by Horn Formulas and Linear Time on Cellular Automata
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.
BibTeX - Entry
@InProceedings{bacquey_et_al:LIPIcs:2017:7417,
author = {Nicolas Bacquey and Etienne Grandjean and Fr{\'e}d{\'e}ric Olive},
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 = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7417},
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 }
}
Keywords: |
|
picture languages, linear time, cellular automata of any dimension, local induction, descriptive complexity, second-order logic, horn formulas, logic |
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
07.07.2017 |