|
Torben Amtoft, Charles Consel, Olivier Danvy, and Karoline
Malmkjær
The abstraction and instantiation
of string-matching programs
Technical Report BRICS RS-01-12, DAIMI, Department of Computer
Science, University of Aarhus, April 2001
An extended version of an essay which appears in The Essence of
Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil
D. Jones, editors T. Mogensen and D. Schmidt and I. H Sudborough, Springer
LNCS 2566, pp 332-357, 2002.
We consider a naive, quadratic string matcher testing whether a pattern occurs in a text; we equip it with a cache mediating its access to the
text; and we abstract the traversal policy of the pattern, the cache, and
the text. We then specialize this abstracted program with respect to a
pattern, using the off-the-shelf partial evaluator Similix.
Instantiating the abstracted program with a left-to-right traversal
policy yields the linear-time behavior of Knuth, Morris and Pratt's
string matcher. Instantiating it with a right-to-left policy yields the
linear-time behavior of Boyer and Moore's string matcher.
[ bib |
.ps.gz |
.pdf.gz |
.pdf ]
Back
This file has been generated by
bibtex2html 1.61
Copyright notice: The documents contained
in these pages are included by the contributing authors as a means to
ensure timely dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein are maintained
by the authors or by other copyright holders, notwithstanding that
they have offered their works here electronically. It is understood that all persons copying this information will
adhere to the terms and constraints invoked by each author's
copyright. These works
may not be reposted without the explicit permission of the copyright
holder.
If you experience problems downloading any of the files above,
it is most likely because your browser does not handle compressed
files correctly.
In particular, Netscape might save the file in the compressed
gz-format with extension .ps or
.pdf (indicating postscript or PDF, resp.). You can work around this by saving the file,
renaming it to .ps.gz or .pdf.gz, and then
uncrompress it.
|
