Language classes defined by time-bounded relativised cellular automata
From MaRDI portal
Publication:4288203
DOI10.1051/ita/1993270504031zbMath0803.68076MaRDI QIDQ4288203
Meena Mahajan, Kamala Krithivasan
Publication date: 19 April 1994
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92459
cellular automata; hierarchy; real-time; linear-time; oracles; relativised complexity classes; tally languages; language recognisers
68Q45: Formal languages and automata
68Q80: Cellular automata (computational aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Systolic trellis automatata †
- On One-Way Cellular Arrays
- One-way bounded cellular automata
- Some results on time-varying and relativised cellular automata*
- Tally languages and complexity classes
- Cellular automata complexity trade-offs