Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series
| dc.creator | Rigo, Michel | |
| dc.date | 1999-11-08 | |
| dc.date | 2000-01-20 | |
| dc.date.accessioned | 2026-07-07T03:24:26Z | |
| dc.date.available | 2026-07-07T03:24:26Z | |
| dc.description | Generalizations of numeration systems in which N is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language L over a finite alphabet A. For these systems, we obtain a characterization of recognizable sets of integers in terms of rational formal series. We also show that, if the complexity of L is Theta (n^q) (resp. if L is the complement of a polynomial language), then multiplication by an integer k preserves recognizability only if k=t^{q+1} (resp. if k is not a power of the cardinality of A) for some integer t. Finally, we obtain sufficient conditions for the notions of recognizability and U-recognizability to be equivalent, where U is some positional numeration system related to a sequence of integers. | |
| dc.description | 34 pages; corrected typos, two sections concerning exponential case and relation with positional systems added | |
| dc.identifier | https://arxiv.org/abs/cs/9911002 | |
| dc.identifier | http://arxiv.org/abs/cs/9911002 | |
| dc.identifier | Theoret. Comput. Sci. 269 (2001) 469--498 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33324 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.1; F.4.3 | |
| dc.title | Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series | |
| dc.type | text |