Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure (Q2893309)

In this paper the authors investigate the syntactic complexity of the language \(0^*\mathrm{rep}_b(m\mathbb{N})\) formed by the expansion in base \(b\) of the multiples of the integer \(m\). An explicit formula for the syntactic complexity for such a language is provided in the following cases: for \(m\) and \(b\) being coprime, the authors also give the syntactic complexity of the language \(0^*\mathrm{rep}_b(X)\) for a generic periodic set \(X\) of period \(m\), if \(m\) is a power of \(b\), and \(m=b^{n}q\) where \(q,b\) are coprime, \(q\geq 2\), \(n\geq 1\). Extending the result of \textit{M. Rigo} and \textit{É. Vandomme} [Lect. Notes Comput. Sci. 6638, 477--488 (2011; Zbl 1330.68178)], the authors give a lower bound for the syntactic complexity of any ultimately periodic set of integers written in base \(b\) and period \(m=db^nq\), where \(q\) and \(b\) are coprime, and the set of prime factors of \(d\) is a subset of the one of \(b\). Finally the obtained results are applied to the decision problem of checking whether or not a \(b\)-recognizable set of integers is ultimately periodic.