Characterizations and computational complexity of systolic trellis automata (Q792091)

Recently, \textit{K. Čulik II, J. Gruska} and \textit{A. Salomaa} [''Systolic trellis automata (for VLSI)'', Int. J. Comput. Math. (to appear)] have introduced the notion of systolic trellis automata. In the paper under review, various types of triangularly shaped trellis automata (roughly speaking, networks of finite processors) both deterministic and non-deterministic ones used as language recognizers have been studied. Their computational power is characterized in terms of suitably restricted Turing machines. These characterizations allow translating of Turing machine programs into programs of systolic trellis automata which is remarkable insofar as systolic trellis automata work to a certain extent in parallel. Further results included concern the Turing machine time and space complexity of language families recognizable by systolic trellis automata.