Automata Approach to Inexact Tree Pattern Matching Using 1-degree Edit Distance

We compare labeled ordered trees based on unit cost 1-degree edit distance that uses operations vertex relabeling, leaf insertion, and leaf deletion. Given an input tree $T$ and a tree pattern $P$, we find all subtrees in $T$ that match $P$ with up to $k$ errors. We show that this problem can be solved by finite automaton when $T$ and $P$ are represented in linear, prefix bar, notation. First, we solve this problem by a pushdown automaton. Then, we show that it can be transformed into a nondeterministic finite automaton due to its restricted use of the pushdown store. We also show a simulation of the nondeterministic finite automaton by dynamic programming.

Recording