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

DOI10.1142/S0129054121420053MaRDI QIDQ6169898zbMATH OpenOpenAlexFDO

Authors 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

cellular automatacomputational complexitylocally testablesublinear-time computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Recommendations

• Sublinear-time language recognition and decision by one-dimensional cellular automata
• scientific article; zbMATH DE number 1512708
• scientific article; zbMATH DE number 1418341
• Fast parallel language recognition by cellular automata
• scientific article; zbMATH DE number 572172
• Fast reversible language recognition using cellular automata
• Recognition of linear-slender context-free languages by real time one-way cellular automata
• Language recognition by reversible partitioned cellular automata
• Language recognition by reversible partitioned cellular automata and iterative arrays
• scientific article; zbMATH DE number 1254096

Cites work

• A characterization of constant-time cellular automata computation
• A taxonomy of problems with fast parallel algorithms
• Algebraic decision procedures for local testability
• Characterizations of locally testable events
• Computational Complexity
• Constructible functions in cellular automata and their applications to hierarchy results
• Extensions of an idea of McNaughton
• Fast parallel language recognition by cellular automata
• Graphs Related to Reversibility and Complexity in Cellular Automata
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• scientific article; zbMATH DE number 21231 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 1254096 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 2134909 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Nondeterministic NC^1 computation
• On uniform circuit complexity
• Parallel language recognition in constant time by cellular automata
• Parity, circuits, and the polynomial-time hierarchy
• Sublinear time algorithms
• Sublinear-time language recognition and decision by one-dimensional cellular automata

Cited in

(4)

• Fast parallel language recognition by cellular automata
• Sublinear-time language recognition and decision by one-dimensional cellular automata
• A Time Hierarchy Theorem for Nondeterministic Cellular Automata
• Pseudorandom generators for sliding-window algorithms

This page was built for publication: Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169898)