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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

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	https://doi.org/10.1007/978-3-319-15579-1_47
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	http://grammars.grlmc.com/LATA2015/

Keywords

Backward pattern matching
Tree linearization
Tree pattern matching
Tree processing

Access to Document

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

Cite this

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 (Eds.), Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings (pp. 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. editor / A.-H. Dediu ; E. Formenti ; C. Martin-Vide ; B. Truthe. Berlin : Springer, 2015. pp. 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 (eds), 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, pp. 599-610, 9th International Conference on Language and Automata Theory and Applications (LATA 2015), Nice, France, 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. ed. / A.-H. Dediu; E. Formenti; C. Martin-Vide; B. Truthe. Berlin: Springer, 2015. p. 599-610 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8977).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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 AH, Formenti E, Martin-Vide C, Truthe B, editors, Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings. Berlin: Springer. 2015. p. 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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this