A property of real-time trellis automata (Q1079372)

If L is a language acceptable by a real-time trellis automaton having N states [for the definition see for instance \textit{K. Culik II}, \textit{J. Gruska} and \textit{A. Salomaa}, Int. J. Comput. Math. 15, 195-212 (1984; Zbl 0571.68041)] and there exist words x, w such that \(xw^*\cap L\) is infinite then there exists a natural k and a natural \(K\leq N^{| x| +1}\) such that for all \(n\geq 0\) the words \(xw^{k+nK}\) belong to L. Making use of this property one can sometimes easily show that a given language is no real-time trellis language. The author illustrates this for \(L_ 1=\{a^ nb^{mn}:\) \(n,m>0\}\), \(L_ 2=\{a^{2^ n}:\) \(n\geq 0\}\), and \(L_ 3=\{a^ p:\) p is a prime\(\}\).