Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
On Abelian Subshifts
verfasst von : Juhani Karhumäki, Svetlana Puzynina, Markus A. Whiteland
Erschienen in: Developments in Language Theory
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Two finite words u and v are called Abelian equivalent if each letter occurs equally many times in both u and v. The Abelian subshift \(\mathcal A_{\varvec{x}}\) of an infinite word \(\varvec{x}\) is the set of infinite words \(\varvec{y}\) such that, for each factor u of \(\varvec{y}\), there exists a factor v of \(\varvec{x}\) which is Abelian equivalent to u. The notion of Abelian subshift gives a characterization of Sturmian words: among binary uniformly recurrent words, Sturmian words are exactly those words for which \(\mathcal A_{\varvec{x}}\) equals the shift orbit closure \(\varOmega _{\varvec{x}}\). On the other hand, the Abelian subshift of the Thue-Morse word contains uncountably many minimal subshifts. In this paper we undertake a general study of Abelian subshifts. In particular, we characterize the Abelian subshifts of recurrent aperiodic balanced words and the Abelian subshifts of ternary words having factor complexity \(n+2\) for all \(n\ge 1\).