One-way bounded cellular automata
From MaRDI portal
Publication:3885226
DOI10.1016/S0019-9958(80)90164-3zbMath0442.68082MaRDI QIDQ3885226
Publication date: 1980
Published in: Information and Control (Search for Journal in Brave)
parallel computationcellular automatacontext-free languagescontext-sensitive languagesreal- time acceptors
Related Items (49)
Closure properties of cellular automata ⋮ One-way cellular automata on Cayley graphs ⋮ One-dimensional pattern generation by cellular automata ⋮ On time reduction and simulation in cellular spaces ⋮ Input-driven languages are linear conjunctive ⋮ A survey of two-dimensional automata theory ⋮ Two-dimensional iterative arrays: Characterizations and applications ⋮ Language classes defined by time-bounded relativised cellular automata ⋮ Counter machines and distributed automata -- a story about exchanging space and time ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Recognition of poly-slender context-free languages by trellis automata ⋮ Power of interconnections and of nondeterminism in regularY-tree systolic automata ⋮ On iterative and cellular tree arrays ⋮ Unnamed Item ⋮ Some results on time-varying and relativised cellular automata* ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A simple P-complete problem and its language-theoretic representations ⋮ Self-verifying Cellular Automata ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Fast one-way cellular automata. ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Shrinking one-way cellular automata ⋮ \(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ Deterministic one-way simulation of two-way real-time cellular automata and its related problems ⋮ The Boolean closure of linear context-free languages ⋮ Fault-tolerant schemes for some systolic systems ⋮ EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES ⋮ One-dimensional pattern generation by cellular automata ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ On real time one-way cellular array ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Theory of cellular automata: a survey ⋮ Iterative arrays with self-verifying communication cell ⋮ Iterative arrays with self-verifying communication cell ⋮ Constructible functions in cellular automata and their applications to hierarchy results ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ Computations on one-dimensional cellular automata ⋮ Real-Time Prime Generators Implemented on Small-State Cellular Automata ⋮ Language equations ⋮ Pushdown cellular automata ⋮ Complexity of One-Way Cellular Automata ⋮ Linear grammars with one-sided contexts and their automaton representation ⋮ Non-deterministic cellular automata and languages ⋮ Computation theoretic aspects of cellular automata ⋮ Systolic trellis automatata † ⋮ Systolic trellis automatat† ⋮ Topological transformations as a tool in the design of systolic networks ⋮ Fast parallel language recognition by cellular automata
This page was built for publication: One-way bounded cellular automata
