Pattern-matching algorithms based on term rewrite systems

Katoen, Joost-Pieter and Nymeyer, Albert (2000) Pattern-matching algorithms based on term rewrite systems. Theoretical Computer Science, 238 (1-2). pp. 439-463. ISSN 0304-3975

PDF
Restricted to UT campus only: Request a copy
211Kb

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.
Item Type:	Article
Copyright:	© 2000 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Formal Methods and Tools (FMT)
Link to this item:	http://purl.utwente.nl/publications/63255
Official URL:	http://dx.doi.org/10.1016/S0304-3975(00)00041-4
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 118692