article

Partial evaluation of pattern matching in strings

Authors:

Charles Consel,

Olivier DanvyAuthors Info & Claims

Information Processing Letters, Volume 30, Issue 2

Pages 79 - 86

https://doi.org/10.1016/0020-0190(89)90113-0

Published: 30 January 1989 Publication History

Abstract

No abstract available.

Cited By

View all

Damouche NMartel MChapoutot A(2015)Impact of Accuracy Optimization on the Convergence of Numerical IterativeźMethodsRevised Selected Papers of the 25th International Symposium on Logic-Based Program Synthesis and Transformation - Volume 952710.1007/978-3-319-27436-2_9(143-160)Online publication date: 13-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-27436-2_9
Rompf TSujeeth AAmin NBrown KJovanovic VLee HJonnalagedda MOlukotun KOdersky M(2013)Optimizing data structures in high-level programsACM SIGPLAN Notices10.1145/2480359.242912848:1(497-510)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2480359.2429128
Rompf TSujeeth AAmin NBrown KJovanovic VLee HJonnalagedda MOlukotun KOdersky MGiacobazzi RCousot R(2013)Optimizing data structures in high-level programsProceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2429069.2429128(497-510)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2429069.2429128
Show More Cited By

Index Terms

Partial evaluation of pattern matching in strings
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Data types and structures
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching

Recommendations

Fast partial evaluation of pattern matching in strings
Proceedings of the ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP 2003) and workshop on partial evaluation and semantics-based program manipulation (PEPM 2003)

We show how to obtain all of Knuth, Morris, and Pratt's linear-time string matcher by partial evaluation of a quadratic-time string matcher with respect to a pattern string. Although it has been known for 15 years how to obtain this linear matcher by ...
Partial evaluation of pattern matching in strings, revisited

Specialization of a string matcher is a canonical example of partial evaluation. A naive implementation of a string matcher repeatedly matches a pattern against every substring of the data string; this operation should intuitively benefit from ...
Fast partial evaluation of pattern matching in strings

We show how to obtain all of Knuth, Morris, and Pratt's linear-time string matcher by specializing a quadratic-time string matcher with respect to a pattern string. Although it has been known for fifteen years how to obtain this linear matcher by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 30, Issue 2

January 1989

50 pages

ISSN:0020-0190

Editor:
G. R. Andrews
Univ. of Arizona, Tucson

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 30 January 1989

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Damouche NMartel MChapoutot A(2015)Impact of Accuracy Optimization on the Convergence of Numerical IterativeźMethodsRevised Selected Papers of the 25th International Symposium on Logic-Based Program Synthesis and Transformation - Volume 952710.1007/978-3-319-27436-2_9(143-160)Online publication date: 13-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-27436-2_9
Rompf TSujeeth AAmin NBrown KJovanovic VLee HJonnalagedda MOlukotun KOdersky M(2013)Optimizing data structures in high-level programsACM SIGPLAN Notices10.1145/2480359.242912848:1(497-510)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2480359.2429128
Rompf TSujeeth AAmin NBrown KJovanovic VLee HJonnalagedda MOlukotun KOdersky MGiacobazzi RCousot R(2013)Optimizing data structures in high-level programsProceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2429069.2429128(497-510)Online publication date: 23-Jan-2013
https://dl.acm.org/doi/10.1145/2429069.2429128
Hernández M(2009)A taxonomy of some right-to-left string-matching algorithmsProceedings of the 18th international conference on Functional and Constraint Logic Programming10.1007/978-3-642-11999-6_6(79-95)Online publication date: 28-Jun-2009
https://dl.acm.org/doi/10.1007/978-3-642-11999-6_6
Danvy OShan CZerny I(2009)J Is for JavaScriptProceedings of the IFIP TC 2 Working Conference on Domain-Specific Languages10.1007/978-3-642-03034-5_1(1-19)Online publication date: 2-Jul-2009
https://dl.acm.org/doi/10.1007/978-3-642-03034-5_1
Glück R(2008)An investigation of Jones optimality and BTI-universal specializersHigher-Order and Symbolic Computation10.1007/s10990-008-9033-521:3(283-309)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1007/s10990-008-9033-5
Ager MDanvy ORohde H(2006)Fast partial evaluation of pattern matching in stringsACM Transactions on Programming Languages and Systems10.1145/1146809.114681228:4(696-714)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1145/1146809.1146812
Danvy ORohde H(2006)On obtaining the Boyer-Moore string-matching algorithm by partial evaluationInformation Processing Letters10.1016/j.ipl.2006.04.00199:4(158-162)Online publication date: 31-Aug-2006
https://dl.acm.org/doi/10.1016/j.ipl.2006.04.001
Ramos JSilva JVidal G(2005)Fast narrowing-driven partial evaluation for inductively sequential programsACM SIGPLAN Notices10.1145/1090189.108639440:9(228-239)Online publication date: 12-Sep-2005
https://dl.acm.org/doi/10.1145/1090189.1086394
Ramos JSilva JVidal GDanvy OPierce B(2005)Fast narrowing-driven partial evaluation for inductively sequential programsProceedings of the tenth ACM SIGPLAN international conference on Functional programming10.1145/1086365.1086394(228-239)Online publication date: 28-Sep-2005
https://dl.acm.org/doi/10.1145/1086365.1086394
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Fast partial evaluation of pattern matching in strings

Partial evaluation of pattern matching in strings, revisited

Fast partial evaluation of pattern matching in strings

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations