Inexact tree pattern matching with 1-degree edit distance using finite automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00363988" target="_blank" >RIV/68407700:21240/23:00363988 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.dam.2023.01.003" target="_blank" >https://doi.org/10.1016/j.dam.2023.01.003</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2023.01.003" target="_blank" >10.1016/j.dam.2023.01.003</a>

Result language

angličtina

Original language name

Inexact tree pattern matching with 1-degree edit distance using finite automata

Original language description

Given an input tree and a tree pattern, the inexact tree pattern matching problem is about finding all subtrees in the input tree that match the tree pattern with up to errors. To measure the number of errors between two labeled ordered trees, we use the 1-degree edit distance that uses operations node relabel, leaf insert, and leaf delete. The proposed solution is based on a finite automaton that reads a given input tree represented in linear, prefix bar, notation. First, we show its construction for a constrained variant of 1-degree edit distance where leaf insert/delete operations cannot be applied to the tree pattern recursively. Then, we extend this approach to both unit cost and non-unit cost 1-degree edit distance. The deterministic version of the proposed finite automaton finds all inexact occurrences of the tree pattern in time linear to the size of the input tree. However, since the size of such automaton can be exponential in the number of nodes of the tree pattern, it is practical only for small patterns. Therefore, we also consider the dynamic programming approach as a way of simulating the nondeterministic finite automaton. This approach comes with the space complexity and time complexity where is the number of nodes of the tree pattern, is the number of nodes of the input tree, and is the maximum number of errors allowed.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

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

Name of the periodical

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Volume of the periodical

330

Issue of the periodical within the volume

May

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

20

Pages from-to

78-97

UT code for WoS article

000924453300001

EID of the result in the Scopus database

2-s2.0-85149786736