Tree template matching in ranked ordered trees by pushdown automata
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F12%3A00196766" target="_blank" >RIV/68407700:21240/12:00196766 - isvavai.cz</a>
Výsledek na webu
<a href="http://www.sciencedirect.com/science/article/pii/S1570866712001384" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1570866712001384</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jda.2012.10.003" target="_blank" >10.1016/j.jda.2012.10.003</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Tree template matching in ranked ordered trees by pushdown automata
Popis výsledku v původním jazyce
We consider the problem of tree template matching in ranked ordered trees, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix notation, and then use pushdown automata as the computational model. The method is analogous to the construction of string pattern matchers. The given tree template is preprocessed once, by constructing a nondeterministic pushdown automaton, which is then transformed to the equivalent deterministic one. Although we prove that the space required for preprocessing is exponential to the size of the tree template in the worst case, the space required for a specific class of tree templates is linear. The time required for the searching phase is linear to the size of the subject tree in both cases.
Název v anglickém jazyce
Tree template matching in ranked ordered trees by pushdown automata
Popis výsledku anglicky
We consider the problem of tree template matching in ranked ordered trees, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix notation, and then use pushdown automata as the computational model. The method is analogous to the construction of string pattern matchers. The given tree template is preprocessed once, by constructing a nondeterministic pushdown automaton, which is then transformed to the equivalent deterministic one. Although we prove that the space required for preprocessing is exponential to the size of the tree template in the worst case, the space required for a specific class of tree templates is linear. The time required for the searching phase is linear to the size of the subject tree in both cases.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2012
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Journal of Discrete Algorithms
ISSN
1570-8667
e-ISSN
—
Svazek periodika
2012
Číslo periodika v rámci svazku
17
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
9
Strana od-do
478-486
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—