Backward linearised tree pattern matching

Jan Trávníček; Jan Janoušek; Bořivoj Melichar; Loek Cleophas

doi:10.1007/978-3-319-15579-1_47

Backward linearised tree pattern matching

Jan Trávníček, Jan Janoušek, Bořivoj Melichar, Loek Cleophas

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

3 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Language and Automata Theory and Applications
Subtitel	9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings
Redacteuren	A.-H. Dediu, E. Formenti, C. Martin-Vide, B. Truthe
Plaats van productie	Berlin
Uitgeverij	Springer
Pagina's	599-610
Aantal pagina's	12
ISBN van geprinte versie	9783319155784
DOI's	https://doi.org/10.1007/978-3-319-15579-1_47
Status	Gepubliceerd - 2015
Evenement	9th International Conference on Language and Automata Theory and Applications (LATA 2015) - Nice, Frankrijk Duur: 2 mrt. 2015 → 6 mrt. 2015 Congresnummer: 9 http://grammars.grlmc.com/LATA2015/

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8977
ISSN van geprinte versie	03029743
ISSN van elektronische versie	16113349

Congres

Congres	9th International Conference on Language and Automata Theory and Applications (LATA 2015)
Verkorte titel	LATA 2015
Land/Regio	Frankrijk
Stad	Nice
Periode	2/03/15 → 6/03/15
Internet adres	http://grammars.grlmc.com/LATA2015/

Toegang tot document

10.1007/978-3-319-15579-1_47

Andere bestanden en links

Link to publication in Scopus

Citeer dit

Trávníček, J., Janoušek, J., Melichar, B., & Cleophas, L. (2015). Backward linearised tree pattern matching. In A-H. Dediu, E. Formenti, C. Martin-Vide, & B. Truthe (editors), Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings (blz. 599-610). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8977). Springer. https://doi.org/10.1007/978-3-319-15579-1_47

Trávníček, Jan ; Janoušek, Jan ; Melichar, Bořivoj et al. / Backward linearised tree pattern matching. Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings. redacteur / A.-H. Dediu ; E. Formenti ; C. Martin-Vide ; B. Truthe. Berlin : Springer, 2015. blz. 599-610 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{90c71bd2bf124ae5a2a91976a7b4f2a0,

title = "Backward linearised tree pattern matching",

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.",

keywords = "Backward pattern matching, Tree linearization, Tree pattern matching, Tree processing",

author = "Jan Tr{\'a}vn{\'i}{\v c}ek and Jan Janou{\v s}ek and Bo{\v r}ivoj Melichar and Loek Cleophas",

year = "2015",

doi = "10.1007/978-3-319-15579-1_47",

language = "English",

isbn = "9783319155784",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "599--610",

editor = "A.-H. Dediu and E. Formenti and C. Martin-Vide and B. Truthe",

booktitle = "Language and Automata Theory and Applications",

address = "Germany",

note = "9th International Conference on Language and Automata Theory and Applications (LATA 2015), LATA 2015 ; Conference date: 02-03-2015 Through 06-03-2015",

url = "http://grammars.grlmc.com/LATA2015/",

}

Trávníček, J, Janoušek, J, Melichar, B & Cleophas, L 2015, Backward linearised tree pattern matching. in A-H Dediu, E Formenti, C Martin-Vide & B Truthe (redactie), Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8977, Springer, Berlin, blz. 599-610, 9th International Conference on Language and Automata Theory and Applications (LATA 2015), Nice, Frankrijk, 2/03/15. https://doi.org/10.1007/978-3-319-15579-1_47

Backward linearised tree pattern matching. / Trávníček, Jan; Janoušek, Jan; Melichar, Bořivoj et al.
Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings. redactie / A.-H. Dediu; E. Formenti; C. Martin-Vide; B. Truthe. Berlin: Springer, 2015. blz. 599-610 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8977).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Backward linearised tree pattern matching

AU - Trávníček, Jan

AU - Janoušek, Jan

AU - Melichar, Bořivoj

AU - Cleophas, Loek

N1 - Conference code: 9

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Backward pattern matching

KW - Tree linearization

KW - Tree pattern matching

KW - Tree processing

UR - http://www.scopus.com/inward/record.url?scp=84928813142&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-15579-1_47

DO - 10.1007/978-3-319-15579-1_47

M3 - Conference contribution

AN - SCOPUS:84928813142

SN - 9783319155784

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 599

EP - 610

BT - Language and Automata Theory and Applications

A2 - Dediu, A.-H.

A2 - Formenti, E.

A2 - Martin-Vide, C.

A2 - Truthe, B.

PB - Springer

CY - Berlin

T2 - 9th International Conference on Language and Automata Theory and Applications (LATA 2015)

Y2 - 2 March 2015 through 6 March 2015

ER -

Trávníček J, Janoušek J, Melichar B, Cleophas L. Backward linearised tree pattern matching. In Dediu A-H, Formenti E, Martin-Vide C, Truthe B, redacteurs, Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings. Berlin: Springer. 2015. blz. 599-610. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-15579-1_47

Backward linearised tree pattern matching

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit