Abstract
The HOM problem, which asks whether the image of a regular tree language under a given tree homomorphism is again regular, is known to be decidable [Godoy & Giménez: The HOM problem is decidable. JACM 60(4), 2013]. However, the problem remains open for regular weighted tree languages. It is demonstrated that the main notion used in the unweighted setting, the tree automaton with equality and inequality constraints, can straightforwardly be generalized to the weighted setting and can represent the image of any regular weighted tree language under any nondeleting, nonerasing tree homomorphism. Several closure properties as well as decision problems are also investigated for the weighted tree languages generated by weighted tree automata with constraints.
Research financially supported by a scholarship awarded to T. Nasz by the Free State of Saxony (Funding no. LAU-R-I-9-2-1021).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bogaert, B., Tison, S.: Equality and disequality constraints on direct subterms in tree automata. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol. 577, pp. 159–171. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55210-3_181
Borchardt, B.: The Theory of Recognizable Tree Series. Ph.D. thesis, Technische Universität Dresden (2005)
Bozapalidis, S., Rahonis, G.: On the closure of recognizable tree series under tree homomorphisms. J. Autom. Lang. Comb. 10(2–3), 185–202 (2005)
Comon, H., et al.: Tree automata – Techniques and applications (2007)
Comon, H., Jacquemard, F.: Ground reducibility and automata with disequality constraints. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 149–162. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-57785-8_138
Dickson, L.E.: Finiteness of the odd perfect and primitive abundant numbers with \(n\) distinct prime factors. Amer. J. Math. 35(4), 413–422 (1913)
Doner, J.: Tree acceptors and some of their applications. J. Comput. System Sci. 4(5), 406–451 (1970)
Drewes, F.: Grammatical Picture Generation: A Tree-Based Approach. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-32507-7
Droste, M., Heusel, D.: The supports of weighted unranked tree automata. Funda. Inform. 136(1–2), 37–58 (2015)
Ésik, Z., Kuich, W.: Formal tree series. J. Autom. Lang. Comb. 8(2), 219–285 (2003)
Fülöp, Z., Maletti, A., Vogler, H.: Preservation of recognizability for synchronous tree substitution grammars. In: Proceedings of the Workshop Applications of Tree Automata in Natural Language Processing, pp. 1–9. ACL (2010)
Fülöp, Z., Maletti, A., Vogler, H.: Weighted extended tree transducers. Fundamenta Informaticae 111(2), 163–202 (2011)
Fülöp, Z., Vogler, H.: Weighted tree automata and tree transducers. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series, pp. 313–403. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01492-5_9
Gécseg, F., Steinby, M.: Tree automata. Technical report 1509.06233, ar**v (2015)
Godoy, G., Giménez, O.: The HOM problem is decidable. J. ACM 60(4), 1–44 (2013)
Golan, J.S.: Semirings and Their Applications. Kluwer Academic, Dordrecht (1999)
Hebisch, U., Weinert, H.J.: Semirings - Algebraic Theory and Applications in Computer Science. World Scientific, Singapore (1998)
Jurafsky, D., Martin, J.H.: Speech and Language Processing, 2nd edn. Prentice Hall, Hoboken (2008)
Kirsten, D.: The support of a recognizable series over a zero-sum free, commutative semiring is recognizable. Acta Cybernet. 20(2), 211–221 (2011)
Mongy-Steen, J.: Transformation de noyaux reconnaissables d’arbres. Forêts RATEG. Ph.D. thesis, Université de Lille (1981)
Perrin, D.: Recent results on automata and infinite words. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol. 176, pp. 134–148. Springer, Heidelberg (1984). https://doi.org/10.1007/BFb0030294
Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Springer, New York (1978). https://doi.org/10.1007/978-1-4612-6264-0
Schützenberger, M.P.: On the definition of a family of automata. Inf. Control 4(2–3), 245–270 (1961)
Thatcher, J.W.: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. J. Comput. Syst. Sci. 1(4), 317–322 (1967)
Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2(1), 57–81 (1968). https://doi.org/10.1007/BF01691346
Tison, S.: Tree automata, (dis-)equality constraints and term rewriting: what’s new? In: Proceedings of the 22nd International Conference on Rewriting Techniques and Applications. LIPIcs, vol. 10, pp. 1–2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
Wang, H.: On characters of semirings. Houston J. Math. 23(3), 391–405 (1997)
Wilhelm, R., Seidl, H., Hack, S.: Compiler Design. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-17540-4
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Maletti, A., Nász, AT. (2022). Weighted Tree Automata with Constraints. In: Diekert, V., Volkov, M. (eds) Developments in Language Theory. DLT 2022. Lecture Notes in Computer Science, vol 13257. Springer, Cham. https://doi.org/10.1007/978-3-031-05578-2_18
Download citation
DOI: https://doi.org/10.1007/978-3-031-05578-2_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-05577-5
Online ISBN: 978-3-031-05578-2
eBook Packages: Computer ScienceComputer Science (R0)