2014/03/25 by Ludovic Mignot, Mignot, Ludovic, Nadia Ouali Sebti +3 · 1 citation
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1403.6251
openalex publication_date 2014/03/25 · arxiv created 2014/07/11 · arxiv updated 2014/07/14 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
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 P due to Glushkov, the c-continuation automaton C due to Champarnaud and Ziadi, the follow automaton F due to Ilie and Yu and the equation automaton E due to Antimirov. It has been shown that P and C are isomorphic and that E (resp. F) is a quotient of C (resp. of P). In this paper, we define from a given regular tree expression the k-position tree automaton P and the follow tree automaton F . Using the definition of the equation tree automaton E of Kuske and Meinecke and our previously defined k-C-continuation tree automaton C, we show that the previous morphic relations are still valid on tree expressions.