Abstract
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 matching using finite tree automata or stringpath matchers and show that it outperforms these for single pattern matching.
Original language | English |
---|---|
Title of host publication | Language and Automata Theory and Applications |
Subtitle of host publication | 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings |
Editors | A.-H. Dediu, E. Formenti, C. Martin-Vide, B. Truthe |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 599-610 |
Number of pages | 12 |
ISBN (Print) | 9783319155784 |
DOIs | |
Publication status | Published - 2015 |
Event | 9th International Conference on Language and Automata Theory and Applications (LATA 2015) - Nice, France Duration: 2 Mar 2015 → 6 Mar 2015 Conference number: 9 http://grammars.grlmc.com/LATA2015/ |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 8977 |
ISSN (Print) | 03029743 |
ISSN (Electronic) | 16113349 |
Conference
Conference | 9th International Conference on Language and Automata Theory and Applications (LATA 2015) |
---|---|
Abbreviated title | LATA 2015 |
Country/Territory | France |
City | Nice |
Period | 2/03/15 → 6/03/15 |
Other | |
Internet address |
Keywords
- Backward pattern matching
- Tree linearization
- Tree pattern matching
- Tree processing