Definability by Horn formulas and linear time on cellular automata - Laboratoire d'informatique fondamentale de Marseille Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Definability by Horn formulas and linear time on cellular automata

Nicolas Bacquey
Etienne Grandjean
  • Fonction : Auteur
  • PersonId : 1004520

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
0.pdf (656.21 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. ICALP 2017 - 44th International Colloquium on Automata, Languages and Programming, Jul 2017, Warsaw, Poland. pp.1-14, ⟨10.4230/LIPIcs.ICALP.2017.99⟩. ⟨hal-01494246v2⟩
1374 Consultations
173 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More