It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base (Q1773328): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jnt.2004.06.005 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1989511011 / rank | |||
Normal rank |
Revision as of 01:10, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base |
scientific article |
Statements
It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base (English)
0 references
28 April 2005
0 references
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)].
0 references
\(\mathbb N\)-rational references
0 references
representation of integers
0 references
\(k\)-recognizability
0 references
slender languages
0 references
Cobham's theorem
0 references