Sequential machine characterizations of trellis and cellular automata and applications. (English) Zbl 0574.68044

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


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)
Full Text: DOI