Linear Recurrence Sequence Automata and the Addition of Abstract Numeration Systems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916716233097216 |
|---|---|
| author | Carton, Olivier Couvreur, Jean-Michel Delacourt, Martin Ollinger, Nicolas |
| author_facet | Carton, Olivier Couvreur, Jean-Michel Delacourt, Martin Ollinger, Nicolas |
| contents | Abstract numeration systems encode natural numbers using radix ordered words of an infinite regular language and linear recurrence sequences play a key role in their valuation. Sequence automata, which are deterministic finite automata with an additional linear recurrence sequence on each transition, are introduced to compute various $\mathbb{Z}$-rational non commutative formal series in abstract numeration systems. Under certain Pisot conditions on the recurrence sequences, the support of these series is regular. This property can be leveraged to derive various synchronized relations including a deterministic finite automaton that computes the addition relation of various Dumont-Thomas numeration systems and deterministic finite automata converting between various numeration systems. A practical implementation for Walnut is provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09868 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear Recurrence Sequence Automata and the Addition of Abstract Numeration Systems Carton, Olivier Couvreur, Jean-Michel Delacourt, Martin Ollinger, Nicolas Formal Languages and Automata Theory Discrete Mathematics Combinatorics Abstract numeration systems encode natural numbers using radix ordered words of an infinite regular language and linear recurrence sequences play a key role in their valuation. Sequence automata, which are deterministic finite automata with an additional linear recurrence sequence on each transition, are introduced to compute various $\mathbb{Z}$-rational non commutative formal series in abstract numeration systems. Under certain Pisot conditions on the recurrence sequences, the support of these series is regular. This property can be leveraged to derive various synchronized relations including a deterministic finite automaton that computes the addition relation of various Dumont-Thomas numeration systems and deterministic finite automata converting between various numeration systems. A practical implementation for Walnut is provided. |
| title | Linear Recurrence Sequence Automata and the Addition of Abstract Numeration Systems |
| topic | Formal Languages and Automata Theory Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2406.09868 |