# zbMATH — the first resource for mathematics

Tree automata constructions from regular expressions: a comparative study. (English) Zbl 1386.68095
Summary: 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 $$\mathcal{P}$$ due to Glushkov, the c-continuation automaton $$\mathcal{C}$$ due to Champarnaud and Ziadi, the follow automaton $$\mathcal F$$ due to Ilie and Yu and the equation automaton $$\mathcal{E}$$ due to Antimirov. It has been shown that $$\mathcal P$$ and $$\mathcal C$$ are isomorphic and that $$\mathcal E$$ (resp. $$\mathcal F$$) is a quotient of $$\mathcal C$$ (resp. of $$\mathcal P$$).
In this paper, we define from a given regular tree expressionthe position tree automaton $$\mathcal P$$ and the follow tree automaton $$\mathcal F$$. Using the definition of the equation tree automaton $$\mathcal E$$ of Kuske and Meinecke and our previously defined c-continuation tree automaton $$\mathcal C$$, we show that the previous morphic relations are still valid on tree expressions.
##### MSC:
 68Q45 Formal languages and automata
Full Text: