Numeration systems on a regular language: arithmetic operations, recognizability and formal power series

作     者：Rigo, M 

作者机构：Univ Liege Inst Math B-4000 Liege Belgium 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2001年第269卷第1-2期

页      面：469-498页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：numeration system recognizability arithmetic operations complexity rational series 

摘      要：Generalizations of numeration systems in which IN is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language L C Sigma (*). For these systems, we obtain a characterization of recognizable sets of integers in terms of N-rational formal series. After a study of the polynomial regular languages, we show that, if the complexity of L is Theta (n(l)) (resp. if L is the complement of a polynomial language), then multiplication by lambda is an element of N preserves recognizability only if lambda = beta (l+1) (resp. if lambda not equal (#Sigma)(beta)) for some beta is an element of N. Finally, we obtain sufficient conditions for the notions of recognizability for abstract systems and some positional number systems to be equivalent. (C) 2001 Elsevier Science B.V. All rights reserved.