Dynamic Deterministic Pattern-Matching
Nadia Nedjah, Luiza de Macedo Mourelle · Electronic Notes in Theoretical Computer Science · 2000
Efficient term matching techniques are pre-requisite for practical term rewriting systems, compilers and interpreters. In previous work, we proposed a new technique to construct deterministic and optimal pattern-matching automata [8–11]. As an important result of our work, we now show how deterministic pattern-matching automata can be constructed incrementally. This is important for applications in which the pattern set changes dynamically. A famous example of such an application is the Knuth-Bendix completion algorithms [7].