Parallel language recognition in constant time by cellular automata

DOI10.1007/BF00290736zbMath0492.68061OpenAlexW1999159632MaRDI QIDQ1168087

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

pattern recognitionparallel computationregular languagescellular spacesarray-languagesconstant time languagesn-dimensional languages

Mathematics Subject Classification ID

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

Related Items (11)

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

Cites Work

• Real-time language recognition by one-dimensional cellular automata
• Classes of languages and linear-bounded automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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