文章基本信息

标题：An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention
本地全文：下载
作者：Bernard Boigelot ; Isabelle Mainz ; Victor Marsault 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：118:1-118:14
DOI：10.4230/LIPIcs.ICALP.2017.118
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be b-recognisable if its representation is a regular language. It is known that eventually periodic sets are b-recognisable in every base b, and Cobham's theorem implies the converse: no other set is b-recognisable in every base b. We are interested in deciding whether a b-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem is decidable in 1986 and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first. In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case.
关键词：integer-base systems; automata; recognisable sets; periodic sets