Some applications of a theorem of Shirshov to language theory. (English) Zbl 0569.68059

A theorem of Shirshov (stating that sufficiently long words over a finite alphabet are either n-divided, or contain a p-th power of a nonempty word) is the basis for three results: a) a characterization of regular languages (using periodicity and a transposition property); b) a characterization of bounded languages (which is in turn applied to regular and context-free languages); c) a sufficient condition for a language to be Parikh-bounded (with a corollary on rational power series).
Reviewer: H.Luchian


68Q45 Formal languages and automata
Full Text: DOI