Backward linearised tree pattern matching

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 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 languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings
EditorsA.-H. Dediu, E. Formenti, C. Martin-Vide, B. Truthe
Place of PublicationBerlin
PublisherSpringer
Pages599-610
Number of pages12
ISBN (Print)9783319155784
DOIs
Publication statusPublished - 2015
Event9th International Conference on Language and Automata Theory and Applications (LATA 2015) - Nice, France
Duration: 2 Mar 20156 Mar 2015
Conference number: 9
http://grammars.grlmc.com/LATA2015/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8977
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference9th International Conference on Language and Automata Theory and Applications (LATA 2015)
Abbreviated titleLATA 2015
CountryFrance
CityNice
Period2/03/156/03/15
Other
Internet address

Fingerprint

Pattern matching
Pattern Matching
Strings
Trees (mathematics)
Ordered Trees
Tree Automata
Linearization
Finite Automata
Matching Algorithm
Table

Keywords

  • Backward pattern matching
  • Tree linearization
  • Tree pattern matching
  • Tree processing

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). Berlin: Springer. https://doi.org/10.1007/978-3-319-15579-1_47
Trávníček, Jan ; Janoušek, Jan ; Melichar, Bořivoj ; Cleophas, Loek. / 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}ček and Jan Janoušek and Boř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",

}

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; Cleophas, Loek.

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 proceedingConference contributionAcademicpeer-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

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

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, 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)). https://doi.org/10.1007/978-3-319-15579-1_47