article · 1993

Science of Computer Programming

Joost-pieter Katoen, Berry Schoenmakersb, Communicated M. Rem

Cited by 0Abstract and details only

Abstract

Let P be a permutation defined on sequences of length N. A sequence of N values is said to be P-invariant when it does not change when permuted according to P. A program is said to recognize P-invariant segments when it determines for each segment of N successive input values whether it is P-invariant. In this paper we derive a program scheme that generates efficient parallel programs for the recognition of P-invariant segments. The programs consist of a chain of cells extended with a linear number of links between non-neighbouring cells. Under reasonable conditions on P. these programs correspond to systolic arrays with both constant response time and constant latency (independent of N). Efficient systolic arrays for problems such as palindrome recogni-tion or perfect shuffle recognition can be constructed automatically in this way. This is illustrated for the palindrome recognition problem.

Cite this paper

APA 7

Katoen, J.-P., Schoenmakersb, B., & Rem, C. M. (1993). Science of Computer Programming.

MLA 9

Katoen, Joost-pieter, et al. “Science of Computer Programming.” 1993.

Chicago

Katoen, Joost-pieter, Berry Schoenmakersb, and Communicated M. Rem. 1993. “Science of Computer Programming.”

Harvard

Katoen, J.-P., Schoenmakersb, B. and Rem, C.M. (1993) ‘Science of Computer Programming’.

BibTeX

@article{katoen1993science,
  title = {{Science of Computer Programming}},
  author = {Katoen, Joost-pieter and Schoenmakersb, Berry and Rem, Communicated M.},
  year = {1993}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.