Definability by Horn formulas and linear time on cellular automata

DOI10.4230/LIPICS.ICALP.2017.99MaRDI QIDQ5111431zbMATH OpenOpenAlexFDO

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

Publication date 27 May 2020

Full work available at URL https://hal.science/hal-01494246

zbMATH Keywords

descriptive complexitylinear timeHorn formulaslogic programmingpicture languagessecond-order logiclocal inductioncellular automata of any dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Decidability of theories and sets of sentences (03B25)

Recommendations

• Descriptive complexity for pictures languages
• A logical approach to locality in pictures languages
• Fast parallel language recognition by cellular automata
• scientific article; zbMATH DE number 3872685
• A characterization of constant-time cellular automata computation

Cited in

(4)

• A logical approach to locality in pictures languages
• Descriptive complexity for minimal time of cellular automata
• Descriptive complexity for pictures languages
• Inductive definitions in logic versus programs of real-time cellular automata

This page was built for publication: Definability by Horn formulas and linear time on cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111431)