Parallel language recognition in constant time by cellular automata

DOI10.1007/BF00290736MaRDI QIDQ1168087zbMATH OpenOpenAlexFDO

Authors R. Sommerhalder, S. C. van Westrhenen

Publication date 1983

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00290736

zbMATH Keywords

array-languagescellular spacesconstant time languagesn-dimensional languagesparallel computationpattern recognitionregular languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80) Pattern recognition, speech recognition (68T10)

Cites work

• Classes of languages and linear-bounded automata
• scientific article; zbMATH DE number 3718546 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3338162 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• scientific article; zbMATH DE number 3386919 (Why is no real title available?)
• Real-time language recognition by one-dimensional cellular automata

Cited in

(12)

• Fast parallel language recognition by cellular automata
• Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars.
• Regular biosequence pattern matching with cellular automata
• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
• Complexity-theoretic aspects of expanding cellular automata
• A characterization of constant-time cellular automata computation
• A logical approach to locality in pictures languages
• On time reduction and simulation in cellular spaces
• Sublinear-time language recognition and decision by one-dimensional cellular automata
• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
• Complexity-theoretic aspects of expanding cellular automata
• Pseudorandom generators for sliding-window algorithms

This page was built for publication: Parallel language recognition in constant time by cellular automata

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