From Tree Automata to Rational Tree Expressions
Younes Guellouma, Hadda Cherroun · International Journal of Foundations of Computer Science · 2018
We propose a construction of rational tree expression from finite tree automata. First, we define rational expression equation systems and we propose a substitution based method to find the unique solution. Furthermore, we discuss the case of recursion being present in an equation system, and then show under which restrictions such systems can effectively be solved. Secondly, we show that any finite tree automaton can be associated to a rational tree equation system, and that the latter can in turn be resolved. Finally, using the previous steps, a rational tree expression equivalent to the underlying automaton is extracted.