HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 6:03:11 PM
Last modification on : Friday, February 4, 2022 - 3:09:08 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 10:45:21 PM


  • HAL Id : inria-00075355, version 1


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



Record views


Files downloads