On real-time cellular automata and trellis automata
From MaRDI portal
Publication:790615
DOI10.1007/BF00264617zbMath0534.68039OpenAlexW2078011493MaRDI QIDQ790615
Christian Choffrut, Karel II Culik
Publication date: 1984
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00264617
Related Items (59)
Closure properties of cellular automata ⋮ A property of real-time trellis automata ⋮ One-way cellular automata on Cayley graphs ⋮ Real time recognition with cellular automata : a meaningful example ⋮ One-dimensional pattern generation by cellular automata ⋮ On time reduction and simulation in cellular spaces ⋮ Boolean grammars ⋮ Real-time, pseudo real-time, and linear-time ITA ⋮ Grids and universal computations on one-dimensional cellular automata ⋮ Effective systolic algorithms for gossiping in cycles and two-dimensional grids ⋮ Language not recognizable in real time by one-way cellular automata ⋮ A survey of two-dimensional automata theory ⋮ Relating the power of cellular arrays to their closure properties ⋮ Language classes defined by time-bounded relativised cellular automata ⋮ Low complexity classes of multidimensional cellular automata ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ Variations of the firing squad problem and applications ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Recognition of poly-slender context-free languages by trellis automata ⋮ Optimal simulation of tree arrays by linear arrays ⋮ On iterative and cellular tree arrays ⋮ Some results on time-varying and relativised cellular automata* ⋮ Efficient unidimensional universal cellular automaton ⋮ Superposable Trellis Automata ⋮ Linear speed-up for cellular automata synchronizers and applications ⋮ Self-verifying Cellular Automata ⋮ Two-dimensional cellular automata and deterministic on-line tessalation automata ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Fast one-way cellular automata. ⋮ Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars. ⋮ On some open problems concerning the complexity of cellular arrays ⋮ Synthesis, structure and power of systolic computations ⋮ Cellular automata with sparse communication ⋮ Iterative tree arrays with logarithmic depth† ⋮ Fault-tolerant schemes for some systolic systems ⋮ The complexity of systolic dissemination of information in interconnection networks ⋮ On hardest languages for one-dimensional cellular automata ⋮ One-dimensional pattern generation by cellular automata ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ On real time one-way cellular array ⋮ A linear speed-up theorem for cellular automata ⋮ Languages not recognizable in real time by one-dimensional cellular automata ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Bulking I: An abstract theory of bulking ⋮ Achieving Universal Computations on One-Dimensional Cellular Automata ⋮ Theory of cellular automata: a survey ⋮ On hardest languages for one-dimensional cellular automata ⋮ Constructible functions in cellular automata and their applications to hierarchy results ⋮ The hardest linear conjunctive language ⋮ Computations on one-dimensional cellular automata ⋮ Pushdown cellular automata ⋮ Signals in one-dimensional cellular automata ⋮ Complexity of One-Way Cellular Automata ⋮ Real-Time Reversible One-Way Cellular Automata ⋮ Different time solutions for the firing squad synchronization problem on basic grid networks ⋮ Iterative tree automata ⋮ A universal cellular automaton in quasi-linear time and its S-m-n form ⋮ Non-deterministic cellular automata and languages ⋮ Topological transformations as a tool in the design of systolic networks
This page was built for publication: On real-time cellular automata and trellis automata
