Prague Stringology Conference 2020
Tomáš Pecka, Jan Trávníček and Jan Janoušek
Conversion of Finite Tree Automata to Regular Tree Expressions By State Elimination
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |