A logical approach to locality in pictures languages
From MaRDI portal
Publication:295631
DOI10.1016/j.jcss.2016.01.005zbMath1342.68183MaRDI QIDQ295631
Etienne Grandjean, Frédéric Olive
Publication date: 13 June 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2016.01.005
cellular automata; monadic second-order logic; linear time; picture languages; recognizability; existential second-order logic; locality and tiling; logical characterizations
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
68Q80: Cellular automata (computational aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Graph properties checkable in linear time in the number of vertices
- A note on the number of monadic quantifiers in monadic \(\Sigma ^{1}_{1}\)
- Finite-model theory -- A personal perspective
- Finite model theory and its applications.
- Elements of finite model theory.
- First-order spectra with one variable
- Parallel language recognition in constant time by cellular automata
- Classifying regular events in symbolic logic
- Capturing complexity classes by fragments of second-order logic
- Computation, logic, philosophy. A collection of essays
- Computations on nondeterministic cellular automata
- Complexity of two-dimensional patterns
- Context-sensitive string languages and recognizable picture languages
- Recognizable picture languages and domino tiling
- Parallel recognition of rational languages in plane cellular automata
- On monadic NP vs monadic co-NP
- Monadic second-order logic over rectangular pictures and recognizability by tiling systems
- On winning Ehrenfeucht games and monadic NP
- On logics with two variables
- The monadic quantifier alternation hierarchy over grids and graphs
- Non-deterministic cellular automata and languages
- ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
- Weak Second‐Order Arithmetic and Finite Automata
- Handbook of Natural Computing
- A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES
- Subshifts, Languages and Logic
- Decision Problems of Finite Automata Design and Related Arithmetics
- Storage Modification Machines
- A spectrum hierarchy
- Monadic generalized spectra
- On languages with two variables
- Separating Nondeterministic Time Complexity Classes
- Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
- Notions of locality and their logical characterizations over finite models
- Regular Graphs and the Spectra of Two-Variable Logic with Counting
- First-order queries on structures of bounded degree are computable with constant delay
- A Time Hierarchy Theorem for Nondeterministic Cellular Automata
- Generalized finite automata theory with an application to a decision problem of second-order logic
- STACS 2005
- Logics with counting and local properties
- Locality of order-invariant first-order formulas
- Logics capturing local properties
- The classical decision problem.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
