Backward Linearised Tree Pattern Matching
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Backward Linearised Tree Pattern Matching
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
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
—
Number of pages
12
Pages from-to
599-610
Publisher name
Springer
Place of publication
Berlin
Event location
Nice
Event date
Mar 2, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—