Abstract
The Parikh matrix, an extension of the Parikh vector for words, is a fundamental concept in combinatorics on words. We investigate M-unambiguity that identifies words with unique Parikh matrices. While the problem of identifying M-unambiguous words for a binary alphabet is solved using a palindromicly amicable relation, it is open for larger alphabets. We propose substitution rules that establish M-equivalence and solve the problem of M-unambiguity for a ternary alphabet. Our rules build on the principles of the palindromicly amicable relation and enable tracking of the differences of length-3 ordered scattered-factors. We characterize the set of M-unambiguous words and obtain a regular expression for the set.
| Original language | English |
|---|---|
| Title of host publication | Implementation and Application of Automata - 27th International Conference, CIAA 2023, Proceedings |
| Editors | Benedek Nagy, Benedek Nagy |
| Publisher | Springer Science and Business Media Deutschland GmbH |
| Pages | 141-152 |
| Number of pages | 12 |
| ISBN (Print) | 9783031402463 |
| DOIs | |
| Publication status | Published - 2023 |
| Event | Implementation and Application of Automata - 27th International Conference, CIAA 2023, Proceedings - Famagusta, Cyprus Duration: 2023 Sept 19 → 2023 Sept 22 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 14151 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | Implementation and Application of Automata - 27th International Conference, CIAA 2023, Proceedings |
|---|---|
| Country/Territory | Cyprus |
| City | Famagusta |
| Period | 23/9/19 → 23/9/22 |
Bibliographical note
Publisher Copyright:© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science