Paper Info
Title
Pattern-matching algorithms based on term rewrite systems
Abstract
Automatic code generators often contain pattern matchers that are based on tree grammars. In this work we generalise this approach by developing pattern matchers that are based on more powerful term rewrite systems. A pattern matcher based on a term rewrite system computes all the sequences of rewrite rules that will reduce a given expression tree to a given goal. While the number of sequences of rewrite rules that are generated is typically enormous, the vast majority of sequences are in fact redundant. This redundancy is caused by the fact that many rewrite sequences are permutations of each other. A theory and a series of algorithms are systematically developed that identify and remove two types of redundant rewrite sequences. These algorithms terminate if rewrite sequences do not diverge.
Year
DOI
Venue
2000
10.1016/S0304-3975(00)00041-4
Theor. Comput. Sci.
Keywords
DocType
Volume
Pattern-matching algorithm,Term rewrite systems,Code generation,Formal techniques,Pattern matching
Journal
238
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
0
PageRank 
References 
Authors
0.34
17
2
Name
Order
Citations
PageRank
Joost-Pieter Katoen14444289.65
Albert Nymeyer21069.98