Semilinear real-time systolic trellis automata. (English) Zbl 0756.68079
Fundamentals of computation theory, Proc. Int. Conf., FCT ’89, Szeged/Hung. 1989, Lect. Notes Comput. Sci. 380, 267-276 (1989).
Summary: [
A real-time systolic trellis automaton (RTSTA) will be called semilinear of degree (at most) \(k\) if its underlying trellis \(T\) is semilinear of degree (at most) \(k\), i.e. the set of rows of \(T\) can be expressed as a finite union of languages of the form \[ \{u_ 0 v_ 1^ i u_ 1 v_ 2^ i u_ 2\dots u_{k-1}v_ k^ i u_ k;\;i\geq 1\}. \] It is proved that every semilinear RTSTA of arbitrary degree \(k\) is equivalent with a semilinear regular RTSTA of degree 3. If regularity is not requested the degree can be diminished to 2, but not to 1.
For the entire collection see [Zbl 0764.20028].
A real-time systolic trellis automaton (RTSTA) will be called semilinear of degree (at most) \(k\) if its underlying trellis \(T\) is semilinear of degree (at most) \(k\), i.e. the set of rows of \(T\) can be expressed as a finite union of languages of the form \[ \{u_ 0 v_ 1^ i u_ 1 v_ 2^ i u_ 2\dots u_{k-1}v_ k^ i u_ k;\;i\geq 1\}. \] It is proved that every semilinear RTSTA of arbitrary degree \(k\) is equivalent with a semilinear regular RTSTA of degree 3. If regularity is not requested the degree can be diminished to 2, but not to 1.
For the entire collection see [Zbl 0764.20028].
MSC:
| 68Q45 | Formal languages and automata |
