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

DOI10.4230/LIPICS.ICALP.2017.118MaRDI QIDQ5111450zbMATH OpenOpenAlexFDO

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

Publication date 27 May 2020

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)

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.

Recommendations

• scientific article; zbMATH DE number 7089069
• Ultimate periodicity of \(b\)-recognisable sets: a quasilinear procedure
• Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure
• scientific article; zbMATH DE number 1929973
• Syntactic complexity of ultimately periodic sets of integers

Cited in

(8)

• scientific article; zbMATH DE number 7453075 (Why is no real title available?)
• Magic Numbers in Periodic Sequences
• Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure
• scientific article; zbMATH DE number 7089069 (Why is no real title available?)
• Syntactic complexity of ultimately periodic sets of integers
• Ultimate periodicity problem for linear numeration systems
• Ultimate periodicity of \(b\)-recognisable sets: a quasilinear procedure
• 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)