Closure properties of cellular automata

DOI10.1016/j.tcs.2005.10.039zbMath1086.68089OpenAlexW2065695636MaRDI QIDQ818118

Véronique Terrier

Publication date: 24 March 2006

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.039

zbMATH Keywords

cellular automataclosure propertiesreal time and linear time classes

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items (7)

Recognition of poly-slender context-free languages by trellis automata ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ \(\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 ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars

Cites Work

• 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
• Variations of the firing squad problem and applications
• Two-dimensional cellular automata recognizer
• Two-dimensional cellular automata and deterministic on-line tessalation automata
• Two-dimensional cellular automata and their neighborhoods
• Real-time recognition of languages on an two-dimensional Archimedean thread
• Real-time language recognition by one-dimensional cellular automata
• On One-Way Cellular Arrays
• One-way bounded cellular automata
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Generation of Primes by a One-Dimensional Real-Time Iterative Array

This page was built for publication: Closure properties of cellular automata