Sequential Machine Characterizations of Trellis and Cellular Automata and Applications

DOI10.1137/0214033zbMath0574.68044OpenAlexW1994377305MaRDI QIDQ3692872

Oscar H. Ibarra, Shlomo Moran, Sam M. Kim

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214033

zbMATH Keywords

Turing machinescellular automatonsystolic trellis automatoncombinational logictime complexity classesinfinite planar array

Mathematics Subject Classification ID

Related Items (27)

Real time recognition with cellular automata : a meaningful example ⋮ On time reduction and simulation in cellular spaces ⋮ Two-dimensional cellular automata and their neighborhoods ⋮ Low complexity classes of multidimensional cellular automata ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs ⋮ On iterative and cellular tree arrays ⋮ Superposable Trellis Automata ⋮ Linear speed-up for cellular automata synchronizers and applications ⋮ Self-verifying Cellular Automata ⋮ On some open problems concerning the complexity of cellular arrays ⋮ Shrinking one-way cellular automata ⋮ Fault-tolerant schemes for some systolic systems ⋮ The complexity of systolic dissemination of information in interconnection networks ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ A linear speed-up theorem for cellular automata ⋮ Bulking I: An abstract theory of bulking ⋮ Iterative arrays with self-verifying communication cell ⋮ Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs ⋮ Parallel turing machines with one-head control units and cellular automata ⋮ Two-dimensional cellular automata recognizer ⋮ Complexity of One-Way Cellular Automata ⋮ Linear grammars with one-sided contexts and their automaton representation ⋮ Non-deterministic cellular automata and languages ⋮ Topological transformations as a tool in the design of systolic networks ⋮ Fast parallel language recognition by cellular automata

This page was built for publication: Sequential Machine Characterizations of Trellis and Cellular Automata and Applications