Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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 language | English |
|---|---|
| Title of host publication | Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings |
| Editors | Christophe Reutenauer, Srecko Brlek |
| Publisher | Springer Nature |
| Pages | 77-88 |
| Number of pages | 12 |
| ISBN (Print) | 9783662531310 |
| DOIs | |
| State | Published - 1 Jan 2016 |
| Event | 20th International Conference on Developments in Language Theory, DLT 2016 - Montreal, Canada Duration: 25 Jul 2016 → 28 Jul 2016 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 9840 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 20th International Conference on Developments in Language Theory, DLT 2016 |
|---|---|
| Country/Territory | Canada |
| City | Montreal |
| Period | 25/07/16 → 28/07/16 |
ID: 35284895