Definability by Horn formulas and linear time on cellular automata

Bacquey, Nicolas; Grandjean, Etienne; Olive, Frédéric

Document type :

Communication dans un congrès avec actes

DOI :

10.4230/LIPIcs.ICALP.2017.99

Title :

Definability by Horn formulas and linear time on cellular automata

Author(s) :

Bacquey, Nicolas [Auteur]
Linking Dynamic Data [LINKS]
Grandjean, Etienne [Auteur]
Equipe AMACC - Laboratoire GREYC - UMR6072
Olive, Frédéric [Auteur]
Laboratoire d'informatique Fondamentale de Marseille [LIF]

Scientific editor(s) :

Ioannis Chatzigiannakis
Piotr Indyk
Fabian Kuhn
Anca Muscholl

Conference title :

ICALP 2017 - 44th International Colloquium on Automata, Languages and Programming

City :

Warsaw

Country :

Pologne

Start date of the conference :

2017-07-10

Publisher :

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

English keyword(s) :

logic programming
second-order logic
descriptive complexity
local induction
picture languages
linear time
Horn formulas
cellular automata of any dimension

HAL domain(s) :

Informatique [cs]/Logique en informatique [cs.LO]
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Requêtes d'Agrégation

Collections :