Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
From MaRDI portal
Publication:6169898
DOI10.1142/s0129054121420053zbMath1518.68223OpenAlexW3190244428MaRDI QIDQ6169898
Publication date: 15 August 2023
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054121420053
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast parallel language recognition by cellular automata
- On uniform circuit complexity
- Parallel language recognition in constant time by cellular automata
- Nondeterministic \(NC^1\) computation
- Characterizations of locally testable events
- A characterization of constant-time cellular automata computation
- Sublinear Time Algorithms
- Parity, circuits, and the polynomial-time hierarchy
- Extensions of an idea of McNaughton
- A taxonomy of problems with fast parallel algorithms
- Algebraic decision procedures for local testability
- Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
- Graphs Related to Reversibility and Complexity in Cellular Automata
- Computational Complexity
- Constructible functions in cellular automata and their applications to hierarchy results
