DOI

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.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 20th International Conference, DLT 2016, Proceedings
РедакторыChristophe Reutenauer, Srecko Brlek
ИздательSpringer Nature
Страницы77-88
Число страниц12
ISBN (печатное издание)9783662531310
DOI
СостояниеОпубликовано - 1 янв 2016
Событие20th International Conference on Developments in Language Theory, DLT 2016 - Montreal, Канада
Продолжительность: 25 июл 201628 июл 2016

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9840
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция20th International Conference on Developments in Language Theory, DLT 2016
Страна/TерриторияКанада
ГородMontreal
Период25/07/1628/07/16

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 35284895