Backward Linearised Tree Pattern Matching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F15%3A00232911" target="_blank" >RIV/68407700:21240/15:00232911 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-15579-1_47" target="_blank" >http://dx.doi.org/10.1007/978-3-319-15579-1_47</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-15579-1_47" target="_blank" >10.1007/978-3-319-15579-1_47</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Backward Linearised Tree Pattern Matching

Popis výsledku v původním jazyce

We present a new backward tree pattern matching algorithm for ordered trees. The algorithm finds all occurrences of a single given tree pattern which match an input tree. It makes use of linearisations of both the given pattern and the input tree. The algorithm preserves the properties and advantages of standard backward string pattern matching approaches. The number of symbol comparisons in the backward tree pattern matching can be sublinear in the size of the input tree. As in the case of backward string pattern matching, the size of the bad character shift table used by the algorithm is linear in the size of the alphabet. We compare the new algorithm with best performing previously existing algorithms based on (non-linearised) tree pattern matchingusing finite tree automata or stringpath matchers and show that it outperforms these for single pattern matching.

Název v anglickém jazyce

Backward Linearised Tree Pattern Matching

Popis výsledku anglicky

We present a new backward tree pattern matching algorithm for ordered trees. The algorithm finds all occurrences of a single given tree pattern which match an input tree. It makes use of linearisations of both the given pattern and the input tree. The algorithm preserves the properties and advantages of standard backward string pattern matching approaches. The number of symbol comparisons in the backward tree pattern matching can be sublinear in the size of the input tree. As in the case of backward string pattern matching, the size of the bad character shift table used by the algorithm is linear in the size of the alphabet. We compare the new algorithm with best performing previously existing algorithms based on (non-linearised) tree pattern matchingusing finite tree automata or stringpath matchers and show that it outperforms these for single pattern matching.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2015

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 statě ve sborníku

Language and Automata Theory and Applications - 9th International Conference, {LATA} 2015, Nice, France, March 2-6, 2015, Proceedings

ISBN

978-3-319-15578-4

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

599-610

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Nice

Datum konání akce

2. 3. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—