TY - GEN

T1 - On Abelian Subshifts

AU - Karhumäki, Juhani

AU - Puzynina, Svetlana

AU - Whiteland, Markus A.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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 Ax of an infinite word x is the set of infinite words y such that, for each factor u of x, there exists a factor v of 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 Ax equals the shift orbit closure. 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=1.

AB - 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 Ax of an infinite word x is the set of infinite words y such that, for each factor u of x, there exists a factor v of 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 Ax equals the shift orbit closure. 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=1.

UR - http://www.scopus.com/inward/record.url?scp=85053919338&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98654-8_37

DO - 10.1007/978-3-319-98654-8_37

M3 - Conference contribution

AN - SCOPUS:85053919338

SN - 9783319986531

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 453

EP - 464

BT - Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings

A2 - Hoshi, Mizuho

A2 - Seki, Shinnosuke

PB - Springer Nature

T2 - 22nd International Conference on Developments in Language Theory, DLT 2018

Y2 - 10 September 2018 through 14 September 2018

ER -