Thumbnail
Access Restriction
Subscribed

Author Bird, R. S.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Recursion elimination ♦ Computational induction ♦ Optimization of programs ♦ Program transformation ♦ Stacks ♦ Pattern matching algorithms
Abstract A new technique of program transformation, called “recursion introduction,” is described and applied to two algorithms which solve pattern matching problems. By using recursion introduction, algorithms which manipulate a stack are first translated into recursive algorithms in which no stack operations occur. These algorithms are then subjected to a second transformation, a method of recursion elimination called “tabulation,” to produce programs with a very efficient running time. In particular, it is shown how the fast linear pattern matching algorithm of Knuth, Morris, and Pratt can be derived in a few steps from a simple nonlinear stack algorithm.
Description Affiliation: Univ. of Reading, Reading, Berkshire, England (Bird, R. S.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 11
Page Count 8
Starting Page 856
Ending Page 863


Open content in new tab

   Open content in new tab
Source: ACM Digital Library