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.
Type de document :
Rapport
[Research Report] RR-1203, INRIA. 1990
Liste complète des métadonnées

https://hal.inria.fr/inria-00075355
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:03:11
Dernière modification le : mercredi 16 mai 2018 - 11:23:02
Document(s) archivé(s) le : mardi 12 avril 2011 - 22:45:21

Fichiers

Identifiants

  • HAL Id : inria-00075355, version 1

Citation

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

Partager

Métriques

Consultations de la notice

361

Téléchargements de fichiers

63