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