Definability by Horn formulas and linear ...
Type de document :
Communication dans un congrès avec actes
Titre :
Definability by Horn formulas and linear time on cellular automata
Auteur(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]
Linking Dynamic Data [LINKS]
Grandjean, Etienne [Auteur]
Equipe AMACC - Laboratoire GREYC - UMR6072
Olive, Frédéric [Auteur]
Laboratoire d'informatique Fondamentale de Marseille [LIF]
Éditeur(s) ou directeur(s) scientifique(s) :
Ioannis Chatzigiannakis
Piotr Indyk
Fabian Kuhn
Anca Muscholl
Piotr Indyk
Fabian Kuhn
Anca Muscholl
Titre de la manifestation scientifique :
ICALP 2017 - 44th International Colloquium on Automata, Languages and Programming
Ville :
Warsaw
Pays :
Pologne
Date de début de la manifestation scientifique :
2017-07-10
Éditeur :
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Mot(s)-clé(s) en anglais :
logic programming
second-order logic
descriptive complexity
local induction
picture languages
linear time
Horn formulas
cellular automata of any dimension
second-order logic
descriptive complexity
local induction
picture languages
linear time
Horn formulas
cellular automata of any dimension
Discipline(s) HAL :
Informatique [cs]/Logique en informatique [cs.LO]
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]/Complexité [cs.CC]
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Projet ANR :
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-01494246v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01494246v2/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01494246v2/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- 0.pdf
- Accès libre
- Accéder au document