6533b860fe1ef96bd12c2e43
RESEARCH PRODUCT
Left-to-right tree pattern matching
Albert Gräfsubject
Set (abstract data type)PrefixFunctional programmingTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESMatching (graph theory)Computer scienceClosure (topology)Point (geometry)Construct (python library)AlgorithmAutomatondescription
We propose a new technique to construct left-to-right matching automata for trees. Our method is based on the novel concept of prefix unifcation which is used to compute a certain closure of the pattern set. From the closure a kind of deterministic matching automaton can be derived immediately. We also point out how to perform the construction incrementally which makes our approach suitable for applications in which pattern sets change dynamically, such as in the Knuth-Bendix completion algorithm.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1991-01-01 |