Caractérisation et programmation en théorie des langages et en logique des classes de complexité efficace des automates cellulaires

Autor: Grente, Theo

Publikováno v: Arithmétique des ordinateurs. Normandie Université, 2020. Français. ⟨NNT : 2020NORMC214⟩

Cellular automata constitute the model of parallel and local computation by excellence.As for any model of parallelism, their programming is known to be difficult. The computingpower of cellular automata, the simplest model of parallelism, is atteste

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od______2592::39408861855d1b66ffddc77637b97322
https://tel.archives-ouvertes.fr/tel-03093951

Backdoors for Linear Temporal Logic

Autor: Irena Schindler, Sebastian Ordyniak, Arne Meier, M. S. Ramanujan

Publikováno v: Leibniz International Proceedings in Informatics, LIPIcs 63 (2017)
Algorithmica

In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of the backd

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ce4e37239adf844b9afab1af9a3648ef

Definability by Horn formulas and linear time on cellular automata

Autor: Bacquey, Nicolas, Grandjean, Etienne, Olive, Frédéric

Publikováno v: ICALP 2017-44th International Colloquium on Automata, Languages and Programming
ICALP 2017-44th International Colloquium on Automata, Languages and Programming, Jul 2017, Warsaw, Poland. pp.1-14, ⟨10.4230/LIPIcs.ICALP.2017.99⟩

International audience; 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 existentia

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::334f9d8dc631b06f115c8b753b112a62
https://hal.science/hal-01494246v2/file/0.pdf

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Bidual Horn functions and extensions

Autor: Toshihide Ibaraki, Thomas Eiter, Kazuhisa Makino

Publikováno v: Discrete Applied Mathematics. :55-88

Partially defined Boolean functions (pdBf) (T,F), where T,F⊆{0,1}n are disjoint sets of true and false vectors, generalize total Boolean functions by allowing that the function values on some input vectors are unknown. The main issue with pdBfs is

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::52cf073d646d37efeb5da74bfaa02ab9