×

Systolic trellis automata: Stability, decidability and complexity. (English) Zbl 0626.68048

Systolic trellis automata have been introduced by the authors [Int. J. Comput. Math. 15, 195-212 (1984; Zbl 0571.68041); ibid. 16, 3-22 (1984; Zbl 0571.68042)].
In this paper for homogeneous (all processors identical) systolic trellis automata it is shown that for any such automaton an equivalent superstable trellis automaton can be constructed (i.e. a trellis automaton which allows to feed an input word to any subsequence of processors on any sufficiently large level). This allows to prove closure properties of the family of languages acceptable by homogeneous trellis automata.
The following problems for homogeneous trellis automata are proved to be undecidable: emptiness, equivalence, superstability.
A trellis automaton is called regular if it has only a finite number of processors and each processor is uniquely determined by its father processors. The family of languages accepted by several subclasses of regular trellis automata are compared with time and space complexity classes of Turing machines. Arbitrary trellis languages belong to \(DSPACE\)-TIME(n,n\({}^ 3)\).
Reviewer: G.Wechsung

MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
68Q80 Cellular automata (computational aspects)
PDF BibTeX XML Cite
Full Text: DOI