Computer Science – Computational Complexity
Scientific paper
1999-11-08
Theoret. Comput. Sci. 269 (2001) 469--498
Computer Science
Computational Complexity
34 pages; corrected typos, two sections concerning exponential case and relation with positional systems added
Scientific paper
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.
No associations
LandOfFree
Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Numeration systems on a regular language: Arithmetic operations, Recognizability and Formal power series will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-61382