Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series

1999/11/30 by Michel Rigo
Computer Science · #cs.CC

paper · pdf

published as Theoret. Comput. Sci. 269 (2001) 469--498 · 34 pages; corrected typos, two sections concerning exponential case and relation with positional systems added

arxiv created 2000/01/20 · arxiv updated 2009/11/30

Abstract

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.

Related

• Numeration systems on a regular language
• Construction of regular languages and recognizability of polynomials
• Generalization of automatic sequences for numeration systems on a regular language
• Linear Recurrence Sequence Automata and the Addition of Abstract Numeration Systems
• Numeration systems without a dominant root and regularity