Prague Stringology Conference 2021
Eliška Šestáková, Ondřej Guth and Jan Janoušek
Automata Approach to Inexact Tree Pattern Matching Using 1-degree Edit Distance
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |