It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base (Q1773328): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
Property / cites work | |||
Property / cites work: Q3994777 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Logic and \(p\)-recognizable sets of integers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weak Second‐Order Arithmetic and Finite Automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the base-dependence of sets of numbers recognizable by finite automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4079524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3997075 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Unrecognizable Sets of Numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3997223 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Thin and slender languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4385527 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4714446 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4155837 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Numeration systems, linear recurrences, and regular sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4205488 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:36, 10 June 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