A Congruence-Based Perspective on Finite Tree Automata

• Autorzy: Ganty Pierre , Gutiérrez Elena , Valero Pedro

Identyfikatory

DOI

10.3233/FI-2021-2091

• Języki publikacji: EN

Abstrakty

EN

We provide new insights on the determinization and minimization of tree automata using congruences on trees. From this perspective, we study a Brzozowski's style minimization algorithm for tree automata. First, we prove correct this method relying on the following fact: when the automata-based and the language-based congruences coincide, determinizing the automaton yields the minimal one. Such automata-based congruences, in the case of word automata, are defined using pre and post operators. Now we extend these operators to tree automata, a task that is particularly challenging due to the reduced expressive power of deterministic top-down (or equivalently co-deterministic bottom-up) automata. We leverage further our framework to offer an extension of the original result by Brzozowski for word automata.

Słowa kluczowe

EN

finite state machines; geometric congruences; congruence lattices

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 184, nr 1
• Strony: 1--47
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Ganty Pierre

• IMDEA Software Institute Madrid, Spain

autor

Gutiérrez Elena

• IMDEA Software Institute Madrid, Spain

autor

Valero Pedro

• IMDEA Software Institute Madrid, Spain

Bibliografia

• [1] Comon H, Dauchet M, Gilleron R, Jacquemard F, Lugiez D, L¨oding C, Tison S, Tommasi M. Tree Automata Techniques and Applications. Available on: http://www.grappa.univ-lille3.fr/tata,2008. Release November, 18th 2008.
• [2] Gécseg F, Steinby M. Minimal ascending tree automata. Acta Cybern., 1978. 4(1):37-44.
• [3] Gécseg F, Steinby M. Tree Automata. Akadéniai Kiad´o, Budapest, Hungary, 1984.
• [4] Abdulla PA, Legay A, d’Orso J, Rezine A. Tree regular model checking: A simulation-based approach. J. Log. Algebraic Methods Program., 2006. 69(1-2):93-121. doi:10.1016/j.jlap.2006.02.001.
• [5] Bouajjani A, Habermehl P, Rogalewicz A, Vojnar T. Abstract regular (tree) model checking. Int. J. Softw. Tools Technol. Transf., 2012. 14(2):167-191. doi:10.1007/s10009-011-0205-y.
• [6] Knight K, May J. Applications of weighted automata in natural language processing. In: Handbook of Weighted Automata, pp. 571-596. Springer, 2009. doi:10.1007 / 978-3-642-01492-5 14.
• [7] Hosoya H. Foundations of XML processing: the tree-automata approach. Cambridge University Press, 2010. doi:10.1017 / CBO9780511762093.
• [8] Abdulla PA, H¨ogberg J, Kaati L. Bisimulation Minimization of Tree Automata. Int. J. Found. Comput. Sci., 2007. 18(4):699-713. doi:10.1142/S0129054107004929.
• [9] Almeida R, Hol´ık L, Mayr R. Reduction of Nondeterministic Tree Automata. In: TACAS, volume 9636 of Lecture Notes in Computer Science. Springer, 2016 pp. 717-735. doi:10.1007/978-3-662-49674-9_46.
• [10] Hogberg J, Maletti A, May J. Backward and forward bisimulation minimization of tree automata. Theor. Comput. Sci., 2009. 410(37):3539-3552. doi:10.1016/j.tcs.2009.03.022.
• [11] Brainerd WS. The Minimalization of Tree Automata. Inf. Control., 1968. 13(5):484-491.
• [12] Björklund J, Cleophas L. A Taxonomy of Minimisation Algorithms for Deterministic Tree Automata. J. UCS, 2016. 22(2):180-196. ISSN:0948-695X.
• [13] Nivat M, Podelski A. Minimal Ascending and Descending Tree Automata. SIAM J. Comput., 1997. 26(1):39-58.
• [14] Virágh J. Deterministic ascending tree automata I. Acta Cybern., 1980. 5(1):33-42.
• [15] Brzozowski JA. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata, 1962. 12(6):529-561. ID:118363215.
• [16] Ganty P, Guti´errez E, Valero P. A Congruence-based Perspective on Automata Minimization Algorithms. In: MFCS, volume 138 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2019 pp. 77:1-77:14.
• [17] Kozen D. On the Myhill-Nerode theorem for trees. Bull. EATCS, 1992. 47:170-173.
• [18] Brzozowski JA, Tamm H. Theory of ´atomata. Theor. Comput. Sci., 2014. 539:13-27. doi:10.1016/j.tcs.2014.04.016.
• [19] Cleophas L. Tree algorithms: two taxonomies and a toolkit. Ph.D. thesis, Department of Mathematics and Computer Science, 2008. doi:10.6100/IR633481.
• [20] Gécseg F, Steinby M. Tree Automata, 2015. 1509.06233.
• [21] Courcelle B, Niwinski D, Podelski A. A Geometrical View of the Determinization and Minimization of Finite-State Automata. Math. Syst. Theory, 1991. 24(2):117-146. doi:10.1007/BF02090394.
• [22] Ganty P, Gutiérrez E, Valero P. A Quasiorder-Based Perspective on Residual Automata. In: MFCS, volume 170 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2020 pp. 40:1-40:14. arXiv:2007.00359 [cs.FL].
• [23] Carme J, Gilleron R, Lemay A, Terlutte A, Tommasi M. Residual Finite Tree Automata. In: Developments in Language Theory, volume 2710 of Lecture Notes in Computer Science. Springer, 2003 pp. 171-182. doi:10.1007 / 3-540-45007-6_13.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)