On hardest languages for one-dimensional cellular automata
From MaRDI portal
Publication:2232270
DOI10.1007/978-3-030-68195-1_10OpenAlexW3131350852MaRDI QIDQ2232270
Alexander Okhotin, Mikhail Mrykhin
Publication date: 4 October 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-68195-1_10
Related Items
The hardest \(\operatorname{LL}(k)\) language, The hardest language for grammars with context operators, The Hardest LL(k) Language, On hardest languages for one-dimensional cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On real time one-way cellular array
- On real-time cellular automata and trellis automata
- Characterizations and computational complexity of systolic trellis automata
- Closure properties of cellular automata
- A property of real-time trellis automata
- On morphic generation of regular languages
- A six-state minimal time solution to the Firing squad synchronization problem
- Relating the power of cellular arrays to their closure properties
- Variations of the firing squad problem and applications
- On time computability of functions in one-way cellular automata
- Language not recognizable in real time by one-way cellular automata
- A tale of conjunctive grammars
- Hardest languages for conjunctive and Boolean grammars
- Boolean grammars
- Recognition of poly-slender context-free languages by trellis automata
- Real-time language recognition by one-dimensional cellular automata
- Non-prinicipalité du cylindre des langages à compteur
- Le cylindre des langages linéaires
- The Hardest Context-Free Language
- Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
- On the equivalence of linear conjunctive grammars and trellis automata
