Tree Automata Constructions from Regular Expressions: a Comparative Study
Ludovic Mignot, Nadia Ouali Sebti, Djelloul Ziadi Β· Fundamenta Informaticae Β· 2017
There exist several methods of computing an automaton recognizing the language denoted by a given regular expression: In the case of words, the position automaton π« due to Glushkov, the c-continuation automaton π due to Champarnaud and Ziadi, the follow automaton β± due to Ilie and Yu and the equation automaton Ι due to Antimirov. It has been shown that π« and π are isomorphic and that Ι (resp. β±) is a quotient of π (resp. of π«). In this paper, we define from a given regular tree expression the position tree automaton π« and the follow tree automaton β±. Using the definition of the equation tree automaton Ι of Kuske and Meinecke and our previously defined c-continuation tree automaton π, we show that the previous morphic relations are still valid on tree expressions.