Positionality of Dumont--Thomas numeration systems for integers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908988294037504 |
|---|---|
| author | Kreczman, Savinien Labbé, Sébastien Stipulanti, Manon |
| author_facet | Kreczman, Savinien Labbé, Sébastien Stipulanti, Manon |
| contents | Introduced in 2001 by Lecomte and Rigo, abstract numeration systems provide a way of expressing natural numbers with words from a language $L$ accepted by a finite automaton. As it turns out, these numeration systems are not necessarily positional, i.e., we cannot always find a sequence $U=(U_i)_{i\ge 0}$ of integers such that the value of every word in the language $L$ is determined by the position of its letters and the first few values of $U$. Finding the conditions under which an abstract numeration system is positional seems difficult in general. In this paper, we thus consider this question for a particular sub-family of abstract numeration systems called Dumont--Thomas numeration systems. They are derived from substitutions and were introduced in 1989 by Dumont and Thomas. We exhibit conditions on the underlying substitution so that the corresponding Dumont--Thomas numeration is positional. We first work in the most general setting, then particularize our results to some practical cases. Finally, we link our numeration systems to existing literature, notably properties studied by Rényi in 1957, Parry in 1960, Bertrand-Mathis in 1989, and Fabre in 1995 |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_04487 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Positionality of Dumont--Thomas numeration systems for integers Kreczman, Savinien Labbé, Sébastien Stipulanti, Manon Combinatorics Discrete Mathematics Formal Languages and Automata Theory 11A67, 11K16, 68R15, 68Q45 Introduced in 2001 by Lecomte and Rigo, abstract numeration systems provide a way of expressing natural numbers with words from a language $L$ accepted by a finite automaton. As it turns out, these numeration systems are not necessarily positional, i.e., we cannot always find a sequence $U=(U_i)_{i\ge 0}$ of integers such that the value of every word in the language $L$ is determined by the position of its letters and the first few values of $U$. Finding the conditions under which an abstract numeration system is positional seems difficult in general. In this paper, we thus consider this question for a particular sub-family of abstract numeration systems called Dumont--Thomas numeration systems. They are derived from substitutions and were introduced in 1989 by Dumont and Thomas. We exhibit conditions on the underlying substitution so that the corresponding Dumont--Thomas numeration is positional. We first work in the most general setting, then particularize our results to some practical cases. Finally, we link our numeration systems to existing literature, notably properties studied by Rényi in 1957, Parry in 1960, Bertrand-Mathis in 1989, and Fabre in 1995 |
| title | Positionality of Dumont--Thomas numeration systems for integers |
| topic | Combinatorics Discrete Mathematics Formal Languages and Automata Theory 11A67, 11K16, 68R15, 68Q45 |
| url | https://arxiv.org/abs/2503.04487 |