Ibarra, Oscar H.; Kim, Sam M.; Moran, Shlomo Sequential machine characterizations of trellis and cellular automata and applications. (English) Zbl 0574.68044 SIAM J. Comput. 14, 426-447 (1985). In this paper a systolic trellis automaton (TA) is an infinite planar array of simple processors of combinational logic with unit propagation delay between neighboring processors. A TA is equivalent to a one- dimensional unbounded cellular automaton (CA). TA’s and CA’s are characterized in terms of full scan Turing machines (STM’s). That is, a language L is accepted by an TA (CA) in time \(n+R(n)\) iff L is accepted by an STM with sweep complexity \((n+1)+R(n)\) for R(n)\(\geq 0\). An STM is a restricted type of on-line Turing machine with a single worktape. The STM characterization is used to prove the speed-up theorem for TA’s (CA’s) and to establishing hierarchies of TA (CA) time complexity classes. Some variations of TA’s (CA’s) and their characterizations are discussed. Reviewer: Renji Tao Cited in 1 ReviewCited in 26 Documents MSC: 68Q80 Cellular automata (computational aspects) 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q25 Analysis of algorithms and problem complexity 68Q45 Formal languages and automata 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) Keywords:systolic trellis automaton; infinite planar array; combinational logic; cellular automaton; Turing machines; time complexity classes PDFBibTeX XMLCite \textit{O. H. Ibarra} et al., SIAM J. Comput. 14, 426--447 (1985; Zbl 0574.68044) Full Text: DOI