Generalization of automatic sequences for numeration systems on a regular language

作     者：Rigo, M 

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

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

年 卷 期：2000年第244卷第1-2期

页      面：271-281页

核心收录：

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

主　　题：automatic sequence numeration system regular language complexity substitution 

摘      要：Let L be an infinite regular language on a totally ordered alphabet (Sigma, ). Feeding a finite deterministic automaton (with output) with the words of L, enumerated lexicographically with respect to , leads to an infinite sequence over the output alphabet of the automaton. This process generalizes the concept of k-automatic sequence for abstract numeration systems on a regular language (instead of systems in base k). Here, we study the first properties of these sequences and their relations with numeration systems. (C) 2000 Elsevier Science B.V. All rights reserved.