Ing. Jan Trávníček, Ph.D.

Publikace

Conversion of Finite Tree Automata to Regular Tree Expressions By State Elimination

Rok
2020
Publikováno
Proceedings of the Prague Stringology Conference 2020. Praha: Czech Technical University in Prague, 2020. p. 11-22. ISBN 978-80-01-06749-9.
Typ
Stať ve sborníku
Anotace
Regular tree languages can be accepted and described by finite tree automata and regular tree expressions, respectively. We describe a new algorithm that converts a finite tree automaton to an equivalent regular tree expression. Our algorithm is analogous to the well-known state elimination method of the conversion of a string finite automaton to an equivalent string regular expression. We define a generalised finite tree automaton, the transitions of which read the sets of trees described by regular tree expressions. Our algorithm eliminates states of the generalised finite tree automaton, which is analogous to the elimination of states in converting the string finite automaton.

Forward Linearised Tree Pattern Matching Using Tree Pattern Border Array

Autoři
Rok
2020
Publikováno
Proceedings of the Prague Stringology Conference 2020. Praha: Czech Technical University in Prague, 2020. p. 61-73. ISBN 978-80-01-06749-9.
Typ
Stať ve sborníku
Anotace
We define a tree pattern border array as a property of linearised trees analogous to border arrays from the string domain. We use it to define a new forward tree pattern matching algorithm for ordered trees, which finds all occurrences of a single given linearised tree pattern in a linearised input tree. As with the classical Morris-Pratt algorithm, the tree pattern border array is used to determine shift lengths in the matching phase of the tree pattern matching algorithm. We compare the new algorithm with the best performing previously existing algorithms based on backward linearised tree pattern matching algorithms, (non-)linearised tree pattern matching algorithms using finite tree automata or stringpath matchers. We show that the presented algorithm outperforms these for single tree pattern matching.

On modification of Boyer-Moore-horspool's algorithm for tree pattern matching in linearised trees

Autoři
Trávníček, J.; Janoušek, J.; Melichar, B.; Cleophas, L.
Rok
2020
Publikováno
Theoretical Computer Science. 2020, 830 60-90. ISSN 0304-3975.
Typ
Článek
Anotace
Tree pattern matching on ordered trees is an important problem in Computer Science. Ordered trees can be represented as strings with additional properties via various linearisations. We present a backward tree pattern matching algorithm for ordered trees for various linear representations of trees and tree patterns. The algorithm adaptations find all occurrences of a single given tree pattern which match an input tree regardless of the chosen linearisation. The algorithms preserve the properties and advantages of standard backward string pattern matching using Boyer-Moore-Horspool's bad character shift heuristics. 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 the string version of Boyer-Moore-Horspool's matching algorithm, the size of the bad character shift table used by the algorithm is linear in the size of the alphabet. We compare the algorithm adaptations with the algorithm using originally chosen linear representation and with the best performing previously existing algorithms based on (non-linearised) tree pattern matching using finite tree automata or stringpath matchers. We show that the presented backward tree pattern matching algorithms outperform the non-linearising ones for single pattern matching and they perform among themselves comparably. (C) 2020 Elsevier B.V. All rights reserved.

Construction of a Pushdown Automaton Accepting a Postfix Notation of a Tree Language Given by a Regular Tree Expression

Autoři
Rok
2018
Publikováno
7th Symposium on Languages, Applications and Technologies (SLATE 2018). Saarbrücken: Dagstuhl Publishing,, 2018. p. 6:1-6:12. ISSN 2190-6807. ISBN 978-3-95977-072-9.
Typ
Stať ve sborníku
Anotace
Regular tree expressions are a formalism for describing regular tree languages, which can be accepted by a finite tree automaton as a standard model of computation. It was proved that the class of regular tree languages is a proper subclass of tree languages those linear notations can be accepted by deterministic string pushdown automata. In this paper, we present a new algorithm for transforming regular tree expressions to equivalent real-time height-deterministic pushdown automata that accept the trees in their postfix notation.

Efficient determinization of visibly and height-deterministic pushdown automata

Autoři
Polách, R.; Trávníček, J.; Janoušek, J.; Melichar, B.
Rok
2016
Publikováno
Computer Languages, Systems and Structures. 2016, 2016(46), 91-105. ISSN 1477-8424.
Typ
Článek
Anotace
New algorithms for the determinization of nondeterministic visibly and nondeterministic real-time height-deterministic pushdown automata are presented. The algorithms improve the results of existing algorithms. They construct only accessible states and necessary pushdown symbols of the resulting deterministic pushdown automata.

A new algorithm for the determinisation of visibly pushdown automata

Autoři
Polách, R.; Trávníček, J.; Janoušek, J.; Melichar, B.
Rok
2015
Publikováno
Proceedings of the 2015 Federated Conference on Computer Science and Information Systems. New York: IEEE, 2015. pp. 915-922. ISSN 2300-5963. ISBN 978-83-60810-65-1.
Typ
Stať ve sborníku
Anotace
Visibly pushdown automata are pushdown automata whose pushdown operations are determined by the input symbol, where the input alphabet is partitioned into three parts for push, pop and local pushdown operations. It is well known that nondeterministic visibly pushdown automata can be determinised. In this paper a new algorithm for the determinisation of nondeterministic visibly pushdown automata is presented. The algorithm improves the existing methods and can result in significantly smaller deterministic pushdown automata. This is achieved in a way that only necessary and accessible states and pushdown symbols are computed and constructed during the determinisation.

Backward Linearised Tree Pattern Matching

Autoři
Trávníček, J.; Janoušek, J.; Melichar, B.; Cleophas, L.
Rok
2015
Publikováno
Language and Automata Theory and Applications - 9th International Conference, {LATA} 2015, Nice, France, March 2-6, 2015, Proceedings. Berlin: Springer, 2015. pp. 599-610. LNCS. ISSN 0302-9743. ISBN 978-3-319-15578-4.
Typ
Stať ve sborníku
Anotace
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.

A Full and Linear Index of a Tree for Tree Patterns

Autoři
Janoušek, J.; Melichar, B.; Polách, R.; Poliak, M.; Trávníček, J.
Rok
2014
Publikováno
DCFS 2014: Proceedings of the 16th International Workshop on Descriptional Complexity of Formal Systems. Berlin: Springer, 2014. pp. 198-209. Lecture Notes in Computer Science. ISSN 0302-9743. ISBN 978-3-319-09703-9.
Typ
Stať ve sborníku
Anotace
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 ).

Indexing ordered trees for (nonlinear) tree pattern matching

Autoři
Rok
2012
Publikováno
COMSIS - Computer Science and Information Systems. 2012, 9(3), 1125-1153. ISSN 1820-0214.
Typ
Článek
Anotace
A new kind of acyclic pushdown automata for an ordered tree is presented. The tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton represent a complete index of the tree for tree patterns and nonlinear tree patterns, respectively. Given a tree with n nodes, the numbers of distinct tree patterns and nonlinear tree patterns whichmatch the tree can be atmost 2n-1+n and at most (2+v)n-1+2, respectively, where v is the maximal number of nonlinear variables allowed in nonlinear tree patterns. The total sizes of nondeterministic versions of the two pushdown automata are O(n) and O(n2), respectively. We discuss the time complexities and show timings of our implementations using the bit-parallelismtechnique. The timings show that for a given tree the running time is linear to the size of the input pattern. The presented pushdown automata are input-driven and therefore can be also determinised.

Indexing Trees by Pushdown Automata for Nonlinear Tree Pattern Matching

Autoři
Rok
2011
Publikováno
FEDCSIS 2011. Los Alamitos: IEEE Computer Society Press, 2011. pp. 871-878. IEEE Catalog Number CFP1185N-USB. ISBN 978-83-60810-22-4.
Typ
Stať ve sborníku
Anotace
A new kind of an acyclic pushdown automaton for an ordered tree is presented. The nonlinear tree pattern pushdown automaton represents a complete index of the tree for nonlinear tree patterns and accepts all nonlinear tree patterns which match the tree. Given a tree with n nodes, the number of such nonlinear tree patterns is O((2+v)n), where v is the number of variables in the patterns. We discuss time and space complexities of the nondeterministic nonlinear tree pattern pushdown automaton and a way of its implementation. The presented pushdown automaton is input-driven and therefore can be determinised.