Undecidability of restricted uniform recurrence equations

1. J.E. Hopcroft, J.D Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, Maaschusetts, 1979.

   MATH  Google Scholar 

2. B. Joinnault: Conception d’algorithmes et d’architectures systoliques. PhD thesis, Université de Rennes, Rennes, France, 1987.

   Google Scholar 

3. H.T. Kung, CE. Leiserson: Algorithms for VLSI processor arrays. In C. Mead, L. Conway (ed.) Introduction to VLSI Systems, Chapter 8.3. Addison-Wesley Publishing Company, 1978.

4. R.M. Karp, R.E. Miller, A. Winograd: The organization of computations for uniform recurrrence equations. Journal of the ACM, 14(3):563–590, 1967.

   Article  MATH  MathSciNet  Google Scholar 

5. H.T. Kung: Why systolic architectures? Computer, 15(l):37–46, 1982.

   Article  Google Scholar 

6. G.M. Megson: Mapping a class of run-time dependencies onto regular arrays. In Proceedings of the International Parallel Processing Symposium, pages 97-105. IEEE, 1993.

7. G.L. Nemhauser, L.A. Wolsey: Integer and Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York, 1989.

   Google Scholar 

8. P. Quinton: Automatic synthesis of systolic arrays from uniform recurence equations. In Proceedings of the Annual International Symposium on Computer Archtecture, pp. 208–214, 1984.

9. P. Quinton, V. van Dongen: The mapping of linear recurrence equations on regular arrays. Journal of VLSI Signal Processing, 1(2):95–113, 1989.

   Article  MATH  Google Scholar 

10. S.V. Rajopadhye: Synthesizing systolic arrays with control signals from recurrence equations. Distributed Computing, 2:88–105, 1989.

    Article  Google Scholar 

11. S.V. Rajopadhye, R.M. Fujimoto: Automating systolic array design. Integration, the VLSI Journal, 9:225–242, 1990.

    Article  Google Scholar 

12. A. Schrijver: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York, 1986.

    Google Scholar 

13. Y. Saouter, P. Quinton: Computability of recurrence equations. Theoretical Computer Science, 116:317–337, 1993.

    Article  MATH  MathSciNet  Google Scholar 

Download references