Skip to Main content Skip to Navigation
Reports

Computability of recurrence equations

Yannick Saouter 1 Patrice Quinton 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : This paper investigates the computability of recurrence equations. We first recall the results established by Karp et al. on the computability of systems of uniform recurrence equations, by Rao on regular iterative arrays and Joinnault's undecidability result on the computability of conditional systems of uniform recurrence equations with non bounded domain. Then we consider systems of parameterized affine recurrence equations, that is to say, systems of recurrence equations whose domains depend linearly on a size parameter and we establish that the computability of such systems is also undecidable.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00075355
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 6:03:11 PM
Last modification on : Thursday, February 11, 2021 - 2:48:03 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 10:45:21 PM

Identifiers

  • HAL Id : inria-00075355, version 1

Citation

Yannick Saouter, Patrice Quinton. Computability of recurrence equations. [Research Report] RR-1203, INRIA. 1990. ⟨inria-00075355⟩

Share

Metrics

Record views

417

Files downloads

201