Language not recognizable in real time by one-way cellular automata

DOI10.1016/0304-3975(95)00111-5zbMath0871.68129OpenAlexW2007670043MaRDI QIDQ1351802

Véronique Terrier

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00111-5

Mathematics Subject Classification ID

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

Related Items

Recognition of poly-slender context-free languages by trellis automata, Inductive definitions in logic versus programs of real-time cellular automata, Fast one-way cellular automata., \(\mathrm{GF}(2)\)-operations on basic families of formal languages, On hardest languages for one-dimensional cellular automata, Languages not recognizable in real time by one-dimensional cellular automata, On hardest languages for one-dimensional cellular automata, Two-dimensional cellular automata recognizer, Complexity of One-Way Cellular Automata

Cites Work

• 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
• Variations of the firing squad problem and applications
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Generation of Primes by a One-Dimensional Real-Time Iterative Array