The bottom-up position tree automaton and the father automaton. (English) Zbl 1458.68082
Summary: 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.
MSC:
| 68Q45 | Formal languages and automata |
Software:
LANGAGEReferences:
| [1] | Adámek, J. and Trnková, V., Automata and Algebras in Categories, (SpringerNetherlands, 1990). · Zbl 0698.18001 |
| [2] | Antimirov, V. M., Partial derivatives of regular expressions and finite automaton constructions, Theor. Comput. Sci.155(2) (1996) 291-319. · Zbl 0872.68120 |
| [3] | Attou, S., Mignot, L. and Ziadi, D., The bottom-up position tree automaton and its compact version, CIAA, , Vol. 10977 (Springer, 2018), pp. 59-70. · Zbl 1458.68081 |
| [4] | Bouchou, B., Duarte, D., Alves, M. H. F., Laurent, D. and Musicante, M. A., Schema evolution for XML: A consistency-preserving approach, MFCS, , Vol. 3153 (Springer, 2004), pp. 876-888. · Zbl 1097.68550 |
| [5] | Broda, S., Holzer, M., Maia, E., Moreira, N. and Reis, R., On the mother of all automata: The position automaton, DLT, , Vol. 10396 (Springer, 2017), pp. 134-146. · Zbl 1494.68130 |
| [6] | Brüggemann-Klein, A. and Wood, D., One-unambiguous regular languages, Inf. Comput.140(2) (1998) 229-253. · Zbl 0895.68146 |
| [7] | Caron, P. and Ziadi, D., Characterization of Glushkov automata, Theor. Comput. Sci.233(1-2) (2000) 75-90. · Zbl 0952.68084 |
| [8] | Champarnaud, J., Mignot, L., Sebti, N. O. and Ziadi, D., Bottom-up quotients for tree languages, J. Automata, Languages and Combinatorics22(4) (2017) 243-269. · Zbl 1393.68090 |
| [9] | Glushkov, V. M., The abstract theory of automata, Russian Mathematical Surveys16 (1961) 1-53. · Zbl 0104.35404 |
| [10] | Högberg, J., Maletti, A. and May, J., Backward and forward bisimulation minimization of tree automata, Theor. Comput. Sci.410(37) (2009) 3539-3552. · Zbl 1194.68139 |
| [11] | Hromkovic, J., Seibert, S. and Wilke, T., Translating regular expressions into small \(\varepsilon \)-free nondeterministic finite automata, J. Comput. Syst. Sci.62(4) (2001) 565-588. · Zbl 1014.68093 |
| [12] | Ilie, L. and Yu, S., Follow automata, Inf. Comput.186(1) (2003) 140-162. · Zbl 1059.68063 |
| [13] | Kuske, D. and Meinecke, I., Construction of tree automata from regular expressions, RAIRO — Theor. Inf. Appl.LEM:ex45(3) (2011) 347-370. · Zbl 1236.68173 |
| [14] | Laugerotte, É., Sebti, N. O. and Ziadi, D., From regular tree expression to position tree automaton, LATA 2013 (2013), pp. 395-406. · Zbl 1377.68116 |
| [15] | McNaughton, R. F. and Yamada, H., Regular expressions and state graphs for automata, IEEE Trans. Electron. Comput.9 (1960) 39-57. · Zbl 0156.25501 |
| [16] | L. Mignot, Application: Tree automata constructions http://ludovicmignot.free.fr/programmes/treeAutCompar/index.html, Accessed: 2018-11-02. |
| [17] | Mignot, L., Sebti, N. O. and Ziadi, D., Tree automata constructions from regular expressions: A comparative study, Fundam. Inform.156(1) (2017) 69-94. · Zbl 1386.68095 |
| [18] | Nicaud, C., On the average size of Glushkov’s automata, LATA, , Vol. 5457 (Springer, 2009), pp. 626-637. · Zbl 1234.68232 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
