Pushdown cellular automata

DOI10.1016/S0304-3975(97)00187-4zbMath0913.68142MaRDI QIDQ1285588

Martin Kutrib

Publication date: 28 April 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexity; cellular automata; parallel computing; formal languages; pushdown storage

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q80: Cellular automata (computational aspects)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

On time reduction and simulation in cellular spaces

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• Relating the power of cellular arrays to their closure properties
• Real-time language recognition by one-dimensional cellular automata
• On One-Way Cellular Arrays
• One-way bounded cellular automata
• On Some Open Problems in the Theory of Cellular Automata
• Real time recognition with cellular automata : a meaningful example
• On the Computational Complexity of Algorithms
• One-way stack automata
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• Tessellation Automata
• Two Families of Languages Related to ALGOL
• Classes of languages and linear-bounded automata
• Three theorems on phrase structure grammars of type 1