Simple Tree Pattern Matching for Trees in the Prefix Bar Notation
Autoři
Lahoda, J.; Žďárek, J.
Rok
2014
Publikováno
Discrete Applied Mathematics. 2014, 163(3), 343-351. ISSN 0166-218X.
Typ
Článek
Pracoviště
Anotace
A pushdown automata based algorithm for searching all occurrences of a tree pattern in a rooted directed labelled ordered subject tree is presented. The algorithm allows tree pattern matching with don't care symbols and with multiple patterns. Further, a construction and practical evaluation of a simulation algorithm of pushdown automata based tree pattern matching is described.
Tree template matching in unranked ordered trees
Autoři
Christou, M.; Flouri, T.; Iliopoulos, C.S.; Janoušek, J.; Melichar, B.; Pissis, S.P.; Žďárek, J.
Rok
2013
Publikováno
Journal of Discrete Algorithms. 2013, 20 51-60. ISSN 1570-8667.
Typ
Článek
Pracoviště
Anotace
We consider the problem of tree template matching, a type of tree pattern matching, where the tree templates have some of their leaves denoted as “donʼt care”, and propose a solution based on the bottom-up technique.
A Note on a Tree-Based 2D Indexing
Autoři
Žďárek, J.; Melichar, B.
Rok
2011
Publikováno
Proceedings of the 15th International Conference on Implementation and Application of Automata. Heidelberg: Springer, 2011. pp. 300-309. Lecture Notes in Computer Science. ISSN 0302-9743. ISBN 978-3-642-18097-2.
Typ
Stať ve sborníku
Pracoviště
Anotace
A transformation of 2D structures into the form of a tree, their linearisation and constructions of pushdown automata indexing this representation of a 2D text are presented.
A Note on a Tree-Based 2D Indexing
Autoři
Žďárek, J.; Melichar, B.
Rok
2011
Publikováno
Lecture Notes in Computer Science. 2011, 2011(6482), 300-309. ISSN 0302-9743.
Typ
Článek
Pracoviště
Anotace
A transformation of 2D structures into the form of a tree, their linearisation and constructions of pushdown automata indexing this representation of a 2D text are presented.
Tree-Based 2D Indexing
Autoři
Žďárek, J.; Melichar, B.
Rok
2011
Publikováno
International Journal of Foundations of Computer Science. 2011, 22(8), 1893-1907. ISSN 0129-0541.
Typ
Článek
Pracoviště
Anotace
A new approach to the 2D pattern matching and specifically to 2D text indexing is proposed. A transformation of a 2D text into the form of a tree is presented. It preserves the context of each element of the 2D text. The tree can be linearised using the prefix notation into the form of a string (a linear text) and the pattern matching is performed in this text. Pushdown automata indexing the 2D text are constructed over the tree representation. They allow to search for 2D prefixes, 2D suffixes, and 2D factors of the 2D text in time proportional to the size of the representation of a 2D pattern. This result achieves the properties analogous to the results obtained in tree pattern matching and string indexing.
A Note on a Tree-based 2D Indexing
Autoři
Žďárek, J.; Melichar, B.
Rok
2010
Publikováno
Pre-proceedings of Conference on Implementation and Application of Automata 2010. Manitoba: University of Manitoba, 2010. pp. 269-277.
Typ
Stať ve sborníku
Pracoviště
Anotace
A transformation of 2D structures into the form of a tree, their linearisation and constructions of pushdown automata indexing this representation of a 2D text are presented.
Simple Tree Pattern Matching for Trees in the Prefix Bar Notation
Autoři
Lahoda, J.; Žďárek, J.
Rok
2010
Publikováno
Proceedings of the Prague Stringology Conference 2010. Praha: České vysoké učení technické v Praze, 2010. pp. 25-36. ISBN 978-80-01-04597-8.
Typ
Stať ve sborníku
Pracoviště
Anotace
A new pushdown automata based algorithm for searching all occurrences of a tree
pattern in a subject tree is presented.
The algorithm allows pattern matching with don't care symbols and multiple patterns.
A simulation algorithm is also proposed, and practical experimental results are
presented.