A Full and Linear Index of a Tree for Tree Patterns

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F14%3A00219874" target="_blank" >RIV/68407700:21240/14:00219874 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-09704-6_18" target="_blank" >http://dx.doi.org/10.1007/978-3-319-09704-6_18</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-09704-6_18" target="_blank" >10.1007/978-3-319-09704-6_18</a>

Result language
angličtina
Original language name
A Full and Linear Index of a Tree for Tree Patterns
Original language description
A new and simple method of indexing a tree for tree patterns is presented. A tree pattern is a tree whose leaves can be labelled by a special symbol S, which serves as a placeholder for any subtree. Given a subject tree T with n nodes, the tree is preprocessed and an index, which consists of a standard string compact suffix automaton and a subtree jump table, is constructed. The number of distinct tree patterns which match the tree is O(2n), and the size of the index is O(n). The searching phase uses the index, reads an input tree pattern P of size m and computes the list of positions of all occurrences of the pattern P in the tree T . For an input tree pattern P in linear prefix notation pref(P) = P1SP2S . . . SPk, k 1, the searching is performed in time O(m+k Pi=1 |occ(Pi)|)), where occ(Pi) is the set of all occurrences of Pi in pref(T ).
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
S - Specificky vyzkum na vysokych skolach

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
DCFS 2014: Proceedings of the 16th International Workshop on Descriptional Complexity of Formal Systems
ISBN
978-3-319-09703-9
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
198-209
Publisher name
Springer
Place of publication
Berlin
Event location
Turku
Event date
Aug 5, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000343868700018

Similar results(10)