Definability by Horn formulas and linear time on cellular automata - Aix-Marseille Université Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2017

Definability by Horn formulas and linear time on cellular automata

Résumé

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.
Fichier principal
Vignette du fichier
BGO.pdf (731.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01494246 , version 1 (23-03-2017)
hal-01494246 , version 2 (22-09-2017)

Identifiants

Citer

Nicolas Bacquey, Etienne Grandjean, Frédéric Olive. Definability by Horn formulas and linear time on cellular automata. 2017. ⟨hal-01494246v1⟩
1374 Consultations
173 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More