zbMATH — the first resource for mathematics

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)
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, (), 37-46
[3] Hilbert, D., Gesammelte abhandlungen, Berlin, 3, (1935) · JFM 61.0022.02
[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, () · Zbl 0604.68027
[10] Rao, S.K., Regular iterative algorithms and their implementations on processor arrays, ()
[11] Saouter, Y.; Quinton, P., Computability of recurrence equations, () · Zbl 0780.65078
[12] Schrijver, A., Theory of linear and integer programming, () · Zbl 0665.90063
[13] Ullman, J.D.; Aho, A.V.; Hopcroft, J.E., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0207.01701
[14] Wong, Y.; Delosme, J.-M., Broadcast removal in systolic algorithms, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.