On hardest languages for one-dimensional cellular automata
From MaRDI portal
Publication:6186307
DOI10.1016/j.ic.2022.104891OpenAlexW4220846211MaRDI QIDQ6186307
Alexander Okhotin, Mikhail Mrykhin
Publication date: 2 February 2024
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2022.104891
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bulking I: An abstract theory of bulking
- Bulking II: Classifications of cellular automata
- Four states are enough!
- 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
- Inducing an order on cellular automata by a grouping operation
- A universal cellular automaton in quasi-linear time and its S-m-n form
- Language not recognizable in real time by one-way cellular automata
- A tale of conjunctive grammars
- Some computational limits of trellis automata
- Hardest languages for conjunctive and Boolean grammars
- Boolean grammars
- On hardest languages for one-dimensional cellular automata
- 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
