Computability of recurrence equations. (English) Zbl 0780.65078

Summary: Systems of uniform recurrence equations were proposed by R. M. Karp et al. [J. Assoc. Comput. Mach. 14, 563–590 (1967; Zbl 0171.38305)] as a tool to derive programs for parallel architectures automatically. Since then, extensions of this formalism were used by many authors, in particular, in the fields of systolic array synthesis. The computability of a system of recurrence equations is, therefore, of primary importance, and is considered as the first point to be examined when trying to implement an algorithm.
This paper investigates the computability of recurrence equations. We first recall the results established by Karp et al. [loc. cit.] on the computability of systems of uniform recurrence equations, by S. K. Rao [Regular iterative algorithms and their implementations on processor arrays. Ph.D. Thesis, Stanford Univ. (1985)] on regular iterative arrays and the undecidability result of B. Joinnault [Conception d’algorithmes et d’architectures systoliques. Thèse, Univ. de Rennes (1987)] on the computability of conditional systems of uniform recurrence equations with nonbounded domain.
Then we consider systems of parametrized affine recurrence equations, that is to say, systems of recurrence equations whose domains linearly depend on a size parameter, and establish that the computability of such systems is also undecidable.


65Q05 Numerical methods for functional equations (MSC2000)
68W15 Distributed algorithms
68Q80 Cellular automata (computational aspects)


Zbl 0171.38305
Full Text: DOI


[1] Delosme, J. M.; Ipsen, I. C.F., Design methodology for systolic arrays, Proc. SPIE 30th Ann. Internat. Tech. Symp. on Optical and Optoelectronic Applied Sciences and Engineering, 245-259 (1986), San Diego, CA
[2] Delosme, J. M.; Ipsen, I. C.F., Efficient systolic arrays for the solution of Toeplitz systems: an illustration of a methodology for the construction of systolic architectures for VLS, (Moore, W.; McCabe, A.; Urquhart, R., Internat. Workshop on Systolic Arrays (1986), Adam Hilger, University of Oxford), 37-46
[3] Hilbert, D., Gesammelte abhandlungen, Berlin, 3 (1935)
[4] Joinnault, B., Conception d’algorithmes et d’architectures systoliques, The“se de l”Universite´de Rennes I (1987)
[5] Karp, R. M.; Miller, R. E.; Winograd, S., The organization of computations for uniform recurrence equations, J. ACM, 14, 563-590 (1967) · Zbl 0171.38305
[6] Matijasevic, Ju. V., Enumerable sets are diophantine, Soviet Math., 11, 354-358 (1970) · Zbl 0212.33401
[7] Quinton, P., Mapping recurrences on parallel architectures, Proc. 3rd Internat. Conf. on Supercomputing, Vol. 3, 1-8 (1988), Boston, MA
[8] Quinton, P.; van Dongen, V., The mapping of linear recurrence equations on regular arrays, The J. VLSI Signal Process., 1, 95-113 (1989) · Zbl 0825.68431
[9] Rajopadhye, S. V.; Fujimoto, R. M., Synthesizing systolic arrays with control signals from recurrence equations, (Tech. Report CIS-TR-86-12 (1987), University of Utah) · Zbl 0604.68027
[10] Rao, S. K., Regular Iterative Algorithms and their Implementations on Processor Arrays, (Ph.D. Thesis (1985), Stanford University)
[11] Saouter, Y.; Quinton, P., Computability of recurrence equations, (Tech. Report 521 (1990), IRISA) · Zbl 0780.65078
[12] Schrijver, A., Theory of Linear and Integer Programming, (Wiley-Interscience Series in Discrete Mathematics (1986), Wiley: Wiley New York) · Zbl 0665.90063
[13] Ullman, J. D.; Aho, A. V.; Hopcroft, J. E., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0207.01701
[14] Wong, Y.; Delosme, J.-M., Broadcast removal in systolic algorithms, (Bromley, K.; Kung, S. Y.; Schwarzlander, E., Proc. Internat. Conf. on Systolic Arrays (1988), IEEE Computer Soc. Press: IEEE Computer Soc. Press Silver Spring, MD), 403-412
[15] Yaacobi, Y.; Cappello, P. R., Scheduling a system of affine recurrence equations onto a systolic array, Internat. Conf. on Systolic Arrays, 373-382 (1988), San Diego, CA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.