It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base (Q1773328): Difference between revisions

A sequence of nonnegative integers, \((a(n))_{n\geq 0}\), is \(\mathbb N\)-rational if there exists a positive integer \(s\) and integer matrices \(V, M, W\) of respective size \(1\times s, s\times s, s\times 1\) such that for all \(n\geq 0\), \(a(n)= VM^n W\). The author proves that, for an \(\mathbb N\)-rational sequence \((a(n))_{n\geq 0}\) it is decidable whether the set \(\{a(n); n\geq 0\}\) is \(k\)-recognizable for some \(k\), and that, in this case, all such bases \(k\) can be determined. Two useful tools are slender languages and Cobham theorem [\textit{A. Cobham's}, Math. Syst. Theory 3, 186--192 (1969; Zbl 0179.02501)].