Tree Automata Constructions from Regular Expressions: a Comparative Study

Article type: Research Article

Authors: Mignot, Ludovic | Sebti, Nadia Ouali | Ziadi, Djelloul^{; *}

Affiliations: Département d’Informatique, Université de Rouen Normandie, 76801 Saint-Étienne du Rouvray Cedex, France. ludovic.mignot@univ-rouen.fr, nadia.ouali-sebti@univ-rouen.fr, djelloul.ziadi@univ-rouen.fr

Correspondence: [*] Address for correspondence: Département d’Informatique, Université de Rouen Normandie, 76801 Saint-Étienne du Rouvray Cedex, France

Abstract: 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.

Keywords: tree automata constructions, regular tree expression, derivatives, partial derivatives, automata theory, c-continuations

DOI: 10.3233/FI-2017-1598

Journal: Fundamenta Informaticae, vol. 156, no. 1, pp. 69-94, 2017