Pattern-matching algorithms based on term rewrite systems

Citation
Jp. Katoen et A. Nymeyer, Pattern-matching algorithms based on term rewrite systems, THEOR COMP, 238(1-2), 2000, pp. 439-464
Citations number
27
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
238
Issue
1-2
Year of publication
2000
Pages
439 - 464
Database
ISI
SICI code
0304-3975(20000506)238:1-2<439:PABOTR>2.0.ZU;2-Z
Abstract
Automatic code generators often contain pattern matchers that are based on tree grammars. In this work we generalise this approach by developing patte rn matchers that are based on mon powerful term rewrite systems, A pattern matcher based on a term rewrite system computes all the sequences of rewrit e 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 enorm ous, 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 tha t identify and remove two types of redundant rewrite sequences. These algor ithms terminate if rewrite sequences do not diverge. (C) 2000 Elsevier Scie nce B.V, All rights reserved.