An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention

DOI10.4230/LIPICS.ICALP.2017.118zbMATH Open1442.68082arXiv1702.03715OpenAlexW2963820659MaRDI QIDQ5111450FDOQ5111450

Isabelle Mainz, Michel Rigo, Victor Marsault, B. Boigelot

Publication date: 27 May 2020

Abstract: Given an integer base $b>1$, a set of integers is represented in base $b$ by a language over $0,1,\mathrm{...},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 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.

Full work available at URL: https://arxiv.org/abs/1702.03715

zbMATH Keywords

automataperiodic setsinteger-base systemsrecognisable sets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata sequences (11B85) Semigroups in automata theory, linguistics, etc. (20M35)

Cited In (6)

• Title not available (Why is that?)
• Magic Numbers in Periodic Sequences
• Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure
• Title not available (Why is that?)
• Ultimate periodicity problem for linear numeration systems
• Minimal automaton for multiplying and translating the Thue-Morse set

This page was built for publication: An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111450)