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\(\}\).
- Some computational limits of trellis automata
- Linear-space recognition for grammars with contexts
- On hardest languages for one-dimensional cellular automata
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- scientific article; zbMATH DE number 17546 (Why is no real title available?)
- scientific article; zbMATH DE number 1836421 (Why is no real title available?)
- Linear grammars with one-sided contexts and their automaton representation
- On hardest languages for one-dimensional cellular automata
- \(\mathrm{GF}(2)\)-operations on basic families of formal languages
- Expressive power of \(\text{LL}(k)\) Boolean grammars
This page was built for publication: A property of real-time trellis automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079372)
