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

cellular automata of any dimensiondescriptive complexityHorn formulaslinear timelocal inductionlogic programmingpicture languagessecond-order logic

Mathematics Subject Classification ID

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

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 pictures languages
• Inductive definitions in logic versus programs of real-time cellular automata
• Descriptive complexity for minimal time of 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)