Constrained Approximate Subtree Matching by Finite Automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F18%3A00323912" target="_blank" >RIV/68407700:21240/18:00323912 - isvavai.cz</a>

Result on the web

<a href="http://www.stringology.org/event/2018/p08.html" target="_blank" >http://www.stringology.org/event/2018/p08.html</a>

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Constrained Approximate Subtree Matching by Finite Automata

Original language description

Processing tree data structures usually requires a pushdown automaton as a model of computation. Therefore, it is interesting that a finite automaton can be used to solve the constrained approximate subtree pattern matching problem. A systematic approach to the construction of such matcher by finite automaton, which reads input trees in prefix bar notation, is presented. Given a tree pattern and an input tree with m and n nodes, respectively, the nondeterministic finite automaton for the pattern is constructed and it is able to find all occurrences of the pattern to subtrees of the input tree with maximum given distance k. The distance between the pattern and subtrees of an input tree is measured by minimal number of restricted tree edit operations, called leaf nodes edit operations. The corresponding deterministic finite automaton finds all occurrences in time O(n) and has O(|A|^k m^(k+1)) states, where A is an alphabet containing all possible node labels. Note that the size is not exponential in the number of nodes of the tree pattern but only in the number of errors. In practice, the number of errors is expected to be a small constant that is much smaller than the size of the pattern. To achieve better space complexity, it is also shown how dynamic programming approach can be used to simulate the nondeterministic automaton. The space complexity of this approach is O(m), while the time complexity is O(mn).

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Prague Stringology Conference 2018

ISBN

978-80-01-06484-9

ISSN

—

e-ISSN

—

Number of pages

12

Pages from-to

79-90

Publisher name

Czech Technical University in Prague

Place of publication

Praha

Event location

Prague

Event date

Aug 27, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—