Indexing ordered trees for (nonlinear) tree pattern matching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F12%3A00196583" target="_blank" >RIV/68407700:21240/12:00196583 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.comsis.org/archive.php?show=vol0903" target="_blank" >http://www.comsis.org/archive.php?show=vol0903</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.2298/CSIS111220024T" target="_blank" >10.2298/CSIS111220024T</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Indexing ordered trees for (nonlinear) tree pattern matching

Popis výsledku v původním jazyce

A new kind of acyclic pushdown automata for an ordered tree is presented. The tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton represent a complete index of the tree for tree patterns and nonlinear tree patterns, respectively. Given a tree with n nodes, the numbers of distinct tree patterns and nonlinear tree patterns whichmatch the tree can be atmost 2n-1+n and at most (2+v)n-1+2, respectively, where v is the maximal number of nonlinear variables allowed in nonlinear tree patterns. The total sizes of nondeterministic versions of the two pushdown automata are O(n) and O(n2), respectively. We discuss the time complexities and show timings of our implementations using the bit-parallelismtechnique. The timings show that for a given tree the running time is linear to the size of the input pattern. The presented pushdown automata are input-driven and therefore can be also determinised.

Název v anglickém jazyce

Indexing ordered trees for (nonlinear) tree pattern matching

Popis výsledku anglicky

A new kind of acyclic pushdown automata for an ordered tree is presented. The tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton represent a complete index of the tree for tree patterns and nonlinear tree patterns, respectively. Given a tree with n nodes, the numbers of distinct tree patterns and nonlinear tree patterns whichmatch the tree can be atmost 2n-1+n and at most (2+v)n-1+2, respectively, where v is the maximal number of nonlinear variables allowed in nonlinear tree patterns. The total sizes of nondeterministic versions of the two pushdown automata are O(n) and O(n2), respectively. We discuss the time complexities and show timings of our implementations using the bit-parallelismtechnique. The timings show that for a given tree the running time is linear to the size of the input pattern. The presented pushdown automata are input-driven and therefore can be also determinised.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

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ů

Název periodika

COMSIS - Computer Science and Information Systems

ISSN

1820-0214

e-ISSN

—

Svazek periodika

9

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

RS - Srbská republika

Počet stran výsledku

29

Strana od-do

1125-1153

Kód UT WoS článku

000309649500007

EID výsledku v databázi Scopus

—