A logical approach to locality in pictures languages
From MaRDI portal
Publication:295631
DOI10.1016/j.jcss.2016.01.005zbMath1342.68183OpenAlexW2296611716MaRDI QIDQ295631
Frédéric Olive, Etienne Grandjean
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 automatamonadic second-order logiclinear timepicture languagesrecognizabilityexistential second-order logiclocality and tilinglogical characterizations
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Cellular automata (computational aspects) (68Q80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Non-expandable non-overlapping sets of pictures, Inductive definitions in logic versus programs of real-time cellular automata, Communication complexity tools on recognizable picture languages
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
