Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata

DOI10.1142/s0129054121420053zbMath1518.68223OpenAlexW3190244428MaRDI QIDQ6169898

Augusto Modanese

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

zbMATH Keywords

computational complexitycellular automatasublinear-time computationlocally testable

Mathematics Subject Classification ID

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