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

    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 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
    Country/TerritoryFrance
    CityNice
    Period2/03/156/03/15
    Other
    Internet address

    Keywords

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

    Fingerprint

    Dive into the research topics of 'Backward linearised tree pattern matching'. Together they form a unique fingerprint.

    Cite this