Fast language acceptance by shrinking cellular automata

DOI10.1016/0020-0255(83)90045-2zbMath0572.68070OpenAlexW2073716439MaRDI QIDQ1062469

Tsvi Dubitzki, Angela Y. Wu, Azriel Rosenfeld

Publication date: 1983

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(83)90045-2

zbMATH Keywords

acceptors for formal languagesbounded cellular automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Related Items (6)

Shrinking and Expanding Cellular Automata ⋮ Shrinking one-way cellular automata ⋮ Non-uniform cellular automata based associative memory: Evolutionary design and basins of attraction ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

Cites Work

• Real-time language recognition by one-dimensional cellular automata
• Unnamed Item

This page was built for publication: Fast language acceptance by shrinking cellular automata