Ing. Tomáš Pecka

Publikace

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

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.