Definability by Horn formulas and linear time on cellular automata

DOI10.4230/LIPICS.ICALP.2017.99zbMATH Open1442.68118OpenAlexW2601070892MaRDI QIDQ5111431FDOQ5111431

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

Publication date: 27 May 2020

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

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

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)

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)