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

automatainteger-base systemsperiodic setsrecognisable sets

Mathematics Subject Classification ID

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

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

(10)

• Minimal automaton for multiplying and translating the Thue-Morse set
• Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure
• Syntactic complexity of ultimately periodic sets of integers
• scientific article; zbMATH DE number 7453075 (Why is no real title available?)
• Ultimate periodicity problem for linear numeration systems
• scientific article; zbMATH DE number 7089069 (Why is no real title available?)
• Ultimate periodicity of b-recognisable sets: a quasilinear procedure
• Magic Numbers in Periodic Sequences
• On the power of ordering in linear arithmetic theories
• An introduction to the theory of linear integer arithmetic (invited paper)

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)