No Cover Image

Journal article 716 views 48 downloads

Decision problems for linear recurrences involving arbitrary real numbers

Eike Neumann

Logical Methods in Computer Science, Volume: 17, Issue: 3, Pages: 16:1 - 16:26

Swansea University Author: Eike Neumann

  • 60145_VoR.pdf

    PDF | Version of Record

    © E. Neumann. This work is licensed under the Creative Commons Attribution License

    Download (530.38KB)

Check full text

DOI (Published version): 10.46298/lmcs-17(3:16)2021

Abstract

We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorith...

Full description

Published in: Logical Methods in Computer Science
ISSN: 1860-5974
Published: Centre pour la Communication Scientifique Directe (CCSD) 2021
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa60145
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorithm which halts for all problem instances for which the answer is locally constant, thus establishing that all three problems are as close to decidable as one can expect them to be in this setting. We further show that the algorithms for the Positivity Problem and the Ultimate Positivity Problem halt on almost every instance with respect to the usual Lebesgue measure on Euclidean space. In comparison, the analogous problems for exact rational or real algebraic coefficients are known to be decidable only for linear recurrences of fairly low order.
Keywords: Skolem Problem, Linear Recurrences, Computable Analysis
College: Faculty of Science and Engineering
Issue: 3
Start Page: 16:1
End Page: 16:26

Similar Items