Sublinear-time language recognition and decision by one-dimensional cellular automata

DOI10.1007/978-3-030-48516-0_19MaRDI QIDQ5041265zbMATH OpenOpenAlexFDO

Authors Augusto Modanese

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
• Fast parallel language recognition by cellular automata
• A characterization of constant-time cellular automata computation
• scientific article; zbMATH DE number 1512708
• scientific article; zbMATH DE number 3872685

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
• Encyclopedia of Complexity and Systems Science
• Extensions of an idea of McNaughton
• Fast parallel language recognition by 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 3561239 (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 1555206 (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

Cited in

(3)

• Fast language acceptance by shrinking cellular automata
• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata

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 Q5041265)