Two words u and v are said to be k-abelian equivalent if, for each word x of length at most k, the number of occurrences of x as a factor of u is the same as for v. We study some combinatorial properties of k-abelian equivalence classes. Our starting point is a characterization of k-abelian equivalence by rewriting, so-called k-switching. We show that the set of lexicographically least representatives of equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is N-rational. We also show that the set of words defining k-abelian singleton classes is regular.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 20th International Conference, DLT 2016, Proceedings
EditorsChristophe Reutenauer, Srecko Brlek
PublisherSpringer Nature
Pages77-88
Number of pages12
ISBN (Print)9783662531310
DOIs
StatePublished - 1 Jan 2016
Event20th International Conference on Developments in Language Theory, DLT 2016 - Montreal, Canada
Duration: 25 Jul 201628 Jul 2016

Publication series

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

Conference

Conference20th International Conference on Developments in Language Theory, DLT 2016
Country/TerritoryCanada
CityMontreal
Period25/07/1628/07/16

    Research areas

  • K-abelian equivalence, Rational sequences, Regular languages

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 35284895