Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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