Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
From MaRDI portal
Publication:5041265
DOI10.1007/978-3-030-48516-0_19OpenAlexW2972546825MaRDI QIDQ5041265
Publication date: 13 October 2022
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.05828
Related Items
Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata, Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
Cites Work
- 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
- Computational Complexity
- Encyclopedia of Complexity and Systems Science
- Constructible functions in cellular automata and their applications to hierarchy results
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
