Definability by Horn formulas and linear time on cellular automata
From MaRDI portal
Publication:5111431
DOI10.4230/LIPIcs.ICALP.2017.99zbMath1442.68118MaRDI QIDQ5111431
Frédéric Olive, Nicolas Bacquey, Etienne Grandjean
Publication date: 27 May 2020
Full work available at URL: https://hal.science/hal-01494246
second-order logic; logic programming; linear time; picture languages; descriptive complexity; Horn formulas; local induction; cellular automata of any dimension
68Q25: Analysis of algorithms and problem complexity
68Q80: Cellular automata (computational aspects)
03B25: Decidability of theories and sets of sentences
Related Items