Tree Automata Constructions from Regular Expressions : a Comparative Study

• Autorzy: Mignot L. , Sebti N. O. , Ziadi D.

Identyfikatory

DOI

10.3233/FI-2017-1598

• Języki publikacji: EN

Abstrakty

EN

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 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 c-continuation tree automaton C, we show that the previous morphic relations are still valid on tree expressions.

Słowa kluczowe

EN

tree automata constructions; regular tree expression; derivatives; partial derivatives; automata theory; c-continuation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 156, nr 1
• Strony: 69--94
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Mignot L.

• Département d’Informatique, Université de Rouen Normandie, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Sebti N. O.

• Département d’Informatique, Université de Rouen Normandie, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Ziadi D.

• Département d’Informatique, Université de Rouen Normandie, 76801 Saint-Étienne du Rouvray Cedex, France

Bibliografia

• [1] Glushkov VM. The abstract theory of automata. Russian Mathematical Surveys, 1961;16:1–53. URL https://doi.org/10.1070/RM1961v016n05ABEH004112.
• [2] Ilie L, Yu S. Follow automata. Inf. Comput., 2003;186(1):140–162. URL https://doi.org/10.1016/S0890-5401(03)00090-7.
• [3] Brzozowski JA. Derivatives of regular expressions. J. ACM, 1964;11(4):481–494. URL http://doi.acm.org/10.1145/321239.321249.
• [4] Antimirov VM. Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci., 1996;155(2):291–319. URL https://doi.org/10.1016/0304-3975(95)00182-4.
• [5] Champarnaud JM, Ziadi D. Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci., 2002;289(1):137–163. URL https://doi.org/10.1016/S0304-3975(01)00267-5.
• [6] García P, López D, Ruiz J, Alvarez GI. From regular expressions to smaller NFAs. Theor. Comput. Sci., 2011;412(41):5802–5807. URL https://doi.org/10.1016/j.tcs.2011.05.058.
• [7] Mignot L, Sebti NO, Ziadi D. k-position, follow, equation and k-c-continuation tree automata constructions. In: Ésik Z, Fülöp Z (eds.), Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 27-29, 2014., volume 151 of EPTCS. 2014 pp. 327–341. URL http://dx.doi.org/10.4204/EPTCS.151.23.
• [8] Kuske D, Meinecke I. Construction of tree automata from regular expressions. RAIRO-Theor. Inf. And Applic., 2011;45(3):347–370. doi:10.1051/ita/2011107 .
• [9] Mignot L, Sebti NO, Ziadi D. An efficient algorithm for the equation tree automaton via the kc-continuations. In: Beckmann A, Csuhaj-Varjú E, Meer K (eds.), Language, Life, Limits-10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings, volume 8493 of Lecture Notes in Computer Science. Springer, 2014 pp. 303–313. URL http://dx.doi.org/10.1007/978-3-319-08019-2_31.
• [10] Laugerotte É, Sebti NO, Ziadi D. From regular tree expression to position tree automaton. In: Dediu AH, Martín-Vide C, Truthe B (eds.), Language and Automata Theory and Applications-7th International Conference, LATA 2013, Bilbao, Spain, April 2-5, 2013. Proceedings, volume 7810 of Lecture Notes in Computer Science. Springer, 2013 pp. 395–406. URL http://dx.doi.org/10.1007/978-3-642-37064-9_35.
• [11] Cortes C, Haffner P, Mohri M. Rational kernels: theory and algorithms. Journal of Machine Learning Research, 2004;5:1035–1062. URL http://dl.acm.org/citation.cfm?id=1005332.1016793.
• [12] Comon H, Dauchet M, Gilleron R, Jacquemard F, Lugiez D, Loding C, Tison S, Tommasi M. Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, 2007.
• [13] Gécseg F, Steinby M. Tree automata. Akadéniai Kiadó, Budapest, Hungary, 1984. ISBN 963-05-3170-4.
• [14] McNaughton R, Yamada H. Regular expressions and state graphs for automata. IEEE Trans. on Electronic Computers, 1960;9(1):39–47. doi:10.1109/TEC.1960.5221603.
• [15] Champarnaud JM, Ziadi D. From c-continuations to new quadratic algorithms for automaton synthesis. IJAC, 2001;11(6):707–736. URL https://doi.org/10.1142/S0218196701000772.
• [16] Khorsi A, Ouardi F, Ziadi D. Fast equation automaton computation. J. Discrete Algorithms, 2008;6(3):433–448. URL https://doi.org/10.1016/j.jda.2007.10.003.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).