One-way bounded cellular automata

DOI10.1016/S0019-9958(80)90164-3MaRDI QIDQ3885226zbMATH OpenFDO

Authors Charles R. Dyer

Publication date 1980

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(80)90164-3

zbMATH Keywords

cellular automatacontext-free languagescontext-sensitive languagesparallel computationreal- time acceptors

Mathematics Subject Classification ID

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

Cited in

(51)

• Topological transformations as a tool in the design of systolic networks
• Fast parallel language recognition by cellular automata
• Two-dimensional iterative arrays: Characterizations and applications
• On iterative and cellular tree arrays
• Deterministic one-way simulation of two-way real-time cellular automata and its related problems
• Pushdown cellular automata
• One-way cellular automata on Cayley graphs
• Fast one-way cellular automata.
• Counter machines and distributed automata -- a story about exchanging space and time
• Theory of cellular automata: a survey
• Computations on one-dimensional cellular automata
• Language equations
• Iterative arrays with self-verifying communication cell
• Recognition of poly-slender context-free languages by trellis automata
• Input-driven languages are linear conjunctive
• A survey of two-dimensional automata theory
• Non-deterministic cellular automata and languages
• Comparing linear conjunctive languages to subfamilies of the context-free languages
• scientific article; zbMATH DE number 3872685 (Why is no real title available?)
• Systolic trellis automatata †
• Systolic trellis automatat†
• Fault-tolerant schemes for some systolic systems
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Some results on time-varying and relativised cellular automata^*
• On time reduction and simulation in cellular spaces
• Language classes defined by time-bounded relativised cellular automata
• On the equivalence of linear conjunctive grammars and trellis automata
• Power of interconnections and of nondeterminism in regularY-tree systolic automata
• Real-Time Prime Generators Implemented on Small-State Cellular Automata
• Unambiguous conjunctive grammars over a one-symbol alphabet
• Complexity of one-way cellular automata
• Linear grammars with one-sided contexts and their automaton representation
• EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
• Constructible functions in cellular automata and their applications to hierarchy results
• On the number of nonterminals in linear conjunctive grammars
• Self-verifying Cellular Automata
• Inductive definitions in logic versus programs of real-time cellular automata
• One-dimensional pattern generation by cellular automata
• A survey of cellular automata: types, dynamics, non-uniformity and applications
• A simple P-complete problem and its language-theoretic representations
• Shrinking one-way cellular automata
• Iterative arrays with self-verifying communication cell
• \(\mathrm{GF}(2)\)-operations on basic families of formal languages
• Nondeterministic, probabilistic and alternating computations on cellular array models
• On real time one-way cellular array
• Cellular automata: from black-and-white to high gloss color
• Context-free, conjunctive and Boolean grammars and SCYK automata
• Computation theoretic aspects of cellular automata
• Closure properties of cellular automata
• One-dimensional pattern generation by cellular automata
• The Boolean closure of linear context-free languages

This page was built for publication: One-way bounded cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3885226)