Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series
<|reference_start|>Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series: 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.<|reference_end|>
@article{rigo1999numeration,
    title={Numeration systems on a regular language: Arithmetic operations,
  Recognizability and Formal power series},
    author={Michel Rigo},
    journal={Theoret. Comput. Sci. 269 (2001) 469--498},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9911002},
    primaryClass={cs.CC}
}