The Bottom-Up Position Tree Automaton and the Father Automaton

被引：1
作者：
Attou, Samira [1 ,2 ]
Mignot, Ludovic [1 ,2 ]
Ziadi, Djelloul [1 ,2 ]
机构：
[1] USTHB, Fac Math, RECITS Lab, BP 32, Algiers 16111, Algeria
[2] Univ Rouen Normandie, Grp Rech Rouennais Informat Fondamentale, Ave Univ, F-76801 St Etienne Du Rouvray, France
来源：
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2020年 / 31卷 / 08期
关键词：
Regular tree expressions; position automaton; top-down; bottom-up; REGULAR EXPRESSIONS;
D O I：
10.1142/S0129054120420034
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The conversion of a given regular tree expression into a tree automaton has been widely studied. However, classical interpretations are based upon a top-down interpretation of tree automata. In this paper, we propose new constructions based on Gluskov's one and on the one by Ilie and Yu using a bottom-up interpretation. One of the main goals of this technique is to consider as a next step the links with deterministic recognizers, something which cannot be done with classical top-down approaches.
引用
收藏
页码：1051 / 1068
页数：18
相关论文
共 18 条
  • [1] Adamek J., 1990, MATH ITS APPL
  • [2] [Anonymous], 1960, IRE Trans. Electron. Comput., DOI [DOI 10.1109/TEC.1960.5221603, 10.1109/TEC.1960.5221603, 10.1109/ TEC.1960.5221603]
  • [3] Partial derivatives of regular expressions and finite automaton constructions
    Antimirov, V
    [J]. THEORETICAL COMPUTER SCIENCE, 1996, 155 (02) : 291 - 319
  • [4] The Bottom-Up Position Tree Automaton and Its Compact Version
    Attou, Samira
    Mignot, Ludovic
    Ziadi, Djelloul
    [J]. IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2018, 2018, 10977 : 59 - 70
  • [5] Bouchou B, 2004, LECT NOTES COMPUT SC, V3153, P876
  • [6] On the Mother of All Automata: The Position Automaton
    Broda, Sabine
    Holzer, Markus
    Maia, Eva
    Moreira, Nelma
    Reis, Rogerio
    [J]. DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017, 2017, 10396 : 134 - 146
  • [7] One-unambiguous regular languages
    Bruggemann-Klein, A
    Wood, D
    [J]. INFORMATION AND COMPUTATION, 1998, 140 (02) : 229 - 253
  • [8] Characterization of Glushkov automata
    Caron, P
    Ziadi, D
    [J]. THEORETICAL COMPUTER SCIENCE, 2000, 233 (1-2) : 75 - 90
  • [9] Champarnaud J.-M., 2017, J AUTOM LANG COMB, P243
  • [10] Glushkov V.M., 1961, Russian Math. Surveys, V16, P1, DOI [10.1070/RM1961v016n05ABEH004112, DOI 10.1070/RM1961V016N05ABEH004112]
12