On Abelian Subshifts

Juhani Karhumäki, Svetlana Puzynina, Markus A. Whiteland

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Scopus citations

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 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.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 22nd International Conference, DLT 2018, Proceedings
EditorsMizuho Hoshi, Shinnosuke Seki
PublisherSpringer Nature
Pages453-464
Number of pages12
ISBN (Print)9783319986531
DOIs
StatePublished - 1 Jan 2018
Event22nd International Conference on Developments in Language Theory, DLT 2018 - Tokyo, Japan
Duration: 10 Sep 201814 Sep 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11088 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on Developments in Language Theory, DLT 2018
CountryJapan
CityTokyo
Period10/09/1814/09/18

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On Abelian Subshifts'. Together they form a unique fingerprint.

Cite this