Inductive definitions in logic versus programs of real-time cellular automata

DOI10.1016/j.tcs.2023.114355OpenAlexW3107368763MaRDI QIDQ6122593

Etienne Grandjean, Théo Grente, Véronique Terrier

Publication date: 1 March 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal-normandie-univ.archives-ouvertes.fr/hal-02474520

zbMATH Keywords

computational complexityinductive logicparallel programmingreal-time computationcellular automatonexistential second-order logicdescriptive complexityHorn formula

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A logical approach to locality in pictures languages
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Finite model theory and its applications.
• Elements of finite model theory.
• On real-time cellular automata and trellis automata
• Low complexity classes of multidimensional cellular automata
• A six-state minimal time solution to the Firing squad synchronization problem
• Variations of the firing squad problem and applications
• Capturing complexity classes by fragments of second-order logic
• Two-dimensional cellular automata recognizer
• Language not recognizable in real time by one-way cellular automata
• Two-dimensional cellular automata and deterministic on-line tessalation automata
• Characterization of real time iterative array by alternating device.
• Some computational limits of trellis automata
• Differences between 2D neighborhoods according to real time computation
• Real-time language recognition by one-dimensional cellular automata
• Handbook of Natural Computing
• Systolic trellis automatata †
• On One-Way Cellular Arrays
• One-way bounded cellular automata
• Distributed Computing: A Locality-Sensitive Approach
• On the equivalence of linear conjunctive grammars and trellis automata
• Communication Complexity
• Definability by Horn formulas and linear time on cellular automata
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• STACS 2005

This page was built for publication: Inductive definitions in logic versus programs of real-time cellular automata