Ing. Tomáš Pecka

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.

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.