On the dimension of the solution space of linear difference equations over the ring of infinite sequences

Sergei Abramov; Gleb Pogudin

doi:10.1016/j.jsc.2024.102350

On the dimension of the solution space of linear difference equations over the ring of infinite sequences

Sergei Abramov
, Gleb Pogudin

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences

Research output: Contribution to journal › Article › peer-review

Abstract

For a linear difference equation with the coefficients being computable sequences, we establish algorithmic undecidability of the problem of determining the dimension of the solution space including the case when some additional prior information on the dimension is available.

Original language	English
Article number	102350
Journal	Journal of Symbolic Computation
Volume	127
DOIs	https://doi.org/10.1016/j.jsc.2024.102350
Publication status	Published - 1 Mar 2025

Keywords

Linear difference operator with sequence coefficients
Solution space dimension
Undecidability

Access to Document

10.1016/j.jsc.2024.102350

Cite this

@article{401f0e7c0f4b481481e7672f1a1a05e4,

title = "On the dimension of the solution space of linear difference equations over the ring of infinite sequences",

abstract = "For a linear difference equation with the coefficients being computable sequences, we establish algorithmic undecidability of the problem of determining the dimension of the solution space including the case when some additional prior information on the dimension is available.",

keywords = "Linear difference operator with sequence coefficients, Solution space dimension, Undecidability",

author = "Sergei Abramov and Gleb Pogudin",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier Ltd",

year = "2025",

month = mar,

day = "1",

doi = "10.1016/j.jsc.2024.102350",

language = "English",

volume = "127",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press",

}

TY - JOUR

T1 - On the dimension of the solution space of linear difference equations over the ring of infinite sequences

AU - Abramov, Sergei

AU - Pogudin, Gleb

PY - 2025/3/1

Y1 - 2025/3/1

N2 - For a linear difference equation with the coefficients being computable sequences, we establish algorithmic undecidability of the problem of determining the dimension of the solution space including the case when some additional prior information on the dimension is available.

AB - For a linear difference equation with the coefficients being computable sequences, we establish algorithmic undecidability of the problem of determining the dimension of the solution space including the case when some additional prior information on the dimension is available.

KW - Linear difference operator with sequence coefficients

KW - Solution space dimension

KW - Undecidability

U2 - 10.1016/j.jsc.2024.102350

DO - 10.1016/j.jsc.2024.102350

M3 - Article

AN - SCOPUS:85197367483

SN - 0747-7171

VL - 127

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

M1 - 102350

ER -

On the dimension of the solution space of linear difference equations over the ring of infinite sequences

Abstract

Keywords

Access to Document

Fingerprint

Cite this