{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:56Z","timestamp":1740109376705,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T00:00:00Z","timestamp":1696291200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T00:00:00Z","timestamp":1696291200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100014913","name":"Freistaat Sachsen","doi-asserted-by":"publisher","award":["LAU-R-I-9-2-1021"],"award-info":[{"award-number":["LAU-R-I-9-2-1021"]}],"id":[{"id":"10.13039\/501100014913","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008678","name":"Universit\u00e4t Leipzig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008678","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 &amp; Gim\u00e9nez: The HOM problem is decidable. JACM\u00a060(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 and 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.<\/jats:p>","DOI":"10.1007\/s00224-023-10144-w","type":"journal-article","created":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T10:03:15Z","timestamp":1696327395000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Weighted Tree Automata with Constraints"],"prefix":"10.1007","volume":"68","author":[{"given":"Andreas","family":"Maletti","sequence":"first","affiliation":[]},{"given":"Andreea-Teodora","family":"N\u00e1sz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,3]]},"reference":[{"key":"10144_CR1","doi-asserted-by":"publisher","unstructured":"Bogaert, B., Tison, S.: Equality and disequality constraints on direct subterms in tree automata. In: A.\u00a0Finkel, M.\u00a0Jantzen (eds.) Proc. 9th Ann. Symp. Theoretical Aspects of Computer Science, LNCS, vol. 577, pp. 161\u2013171. Springer (1992). https:\/\/doi.org\/10.1007\/3-540-55210-3_181","DOI":"10.1007\/3-540-55210-3_181"},{"key":"10144_CR2","unstructured":"Borchardt, B.: The theory of recognizable tree series. Ph.D. thesis, Technische Universit\u00e4t Dresden (2005)"},{"key":"10144_CR3","doi-asserted-by":"publisher","unstructured":"Bozapalidis, S., Rahonis, G.: On the closure of recognizable tree series under tree homomorphisms. J. Autom. Lang. Comb. 10(2\u20133), 185\u2013202 (2005). https:\/\/doi.org\/10.25596\/jalc-2005-185","DOI":"10.25596\/jalc-2005-185"},{"key":"10144_CR4","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata \u2014Techniques and applications. (2007) http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"10144_CR5","doi-asserted-by":"publisher","unstructured":"Comon, H., Jacquemard, F.: Ground reducibility and automata with disequality constraints. In: P.\u00a0Enjalbert, E.W. Mayr, K.W. Wagner (eds.) Proc. 11th Ann. Symp. Theoretical Aspects of Computer Science, LNCS, vol. 775, pp. 151\u2013162, Springer (1994). https:\/\/doi.org\/10.1007\/3-540-57785-8_138","DOI":"10.1007\/3-540-57785-8_138"},{"issue":"4","key":"10144_CR6","doi-asserted-by":"publisher","first-page":"413","DOI":"10.2307\/2370405","volume":"35","author":"LE Dickson","year":"1913","unstructured":"Dickson, L.E.: Finiteness of the odd perfect and primitive abundant numbers with $$n$$ distinct prime factors. Amer. J. Math. 35(4), 413\u2013422 (1913). https:\/\/doi.org\/10.2307\/2370405","journal-title":"Amer. J. Math."},{"issue":"5","key":"10144_CR7","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J Doner","year":"1970","unstructured":"Doner, J.: Tree acceptors and some of their applications. J. Comput. System Sci. 4(5), 406\u2013451 (1970). https:\/\/doi.org\/10.1016\/S0022-0000(70)80041-1","journal-title":"J. Comput. System Sci."},{"key":"10144_CR8","doi-asserted-by":"publisher","unstructured":"Drewes, F.: Grammatical picture generation: A tree-based approach. In: Theoretical Computer Science \u2014 An EATCS Series, vol. 201, Springer (2006). https:\/\/doi.org\/10.1007\/3-540-32507-7","DOI":"10.1007\/3-540-32507-7"},{"issue":"1\u20132","key":"10144_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.3233\/FI-2015-1143","volume":"136","author":"M Droste","year":"2015","unstructured":"Droste, M., Heusel, D.: The supports of weighted unranked tree automata. Funda. Inform. 136(1\u20132), 37\u201358 (2015). https:\/\/doi.org\/10.3233\/FI-2015-1143","journal-title":"Funda. Inform."},{"key":"10144_CR10","doi-asserted-by":"publisher","unstructured":"\u00c9sik, Z., Kuich, W.: Formal tree series. J. Autom. Lang. Comb. 8(2), 219\u2013285 (2003). https:\/\/doi.org\/10.25596\/jalc-2003-219","DOI":"10.25596\/jalc-2003-219"},{"key":"10144_CR11","unstructured":"F\u00fcl\u00f6p, Z., Maletti, A., Vogler, H.: Preservation of recognizability for synchronous tree substitution grammars. In: F.\u00a0Drewes, M.\u00a0Kuhlmann (eds.) Proc. Workshop Applications of Tree Automata in Natural Language Processing, pp. 1\u20139, ACL(2010)"},{"issue":"2","key":"10144_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.3233\/FI-2011-559","volume":"111","author":"Z F\u00fcl\u00f6p","year":"2011","unstructured":"F\u00fcl\u00f6p, Z., Maletti, A., Vogler, H.: Weighted extended tree transducers. Fundam. Inform. 111(2), 163\u2013202 (2011). https:\/\/doi.org\/10.3233\/FI-2011-559","journal-title":"Inform."},{"key":"10144_CR13","doi-asserted-by":"publisher","unstructured":"F\u00fcl\u00f6p, Z., Vogler, H.: Weighted tree automata and tree transducers. In: M.\u00a0Droste, W.\u00a0Kuich, H.\u00a0Vogler (eds.) Handbook of Weighted Automata, Monographs in Theoretical Computer Science \u2014 An EATCS Series, chap.\u00a09, pp. 313\u2013403. Springer, (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_9","DOI":"10.1007\/978-3-642-01492-5_9"},{"key":"10144_CR14","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree automata. Tech. Rep. (2015) arXiv:1509.06233"},{"issue":"4","key":"10144_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2508028.2501600","volume":"60","author":"G Godoy","year":"2013","unstructured":"Godoy, G., Gim\u00e9nez, O.: The HOM problem is decidable. J. ACM 60(4), 1\u201344 (2013). https:\/\/doi.org\/10.1145\/2508028.2501600","journal-title":"J. ACM"},{"key":"10144_CR16","doi-asserted-by":"publisher","unstructured":"Golan, J.S.: Semirings and their Applications. Kluwer Academic, Dordrecht (1999) https:\/\/doi.org\/10.1007\/978-94-015-9333-5","DOI":"10.1007\/978-94-015-9333-5"},{"key":"10144_CR17","doi-asserted-by":"publisher","unstructured":"Hebisch, U., Weinert, H.J.: Semirings\u2013Algebraic Theory and Applications in Computer Science, Series in Algebra, vol.\u00a05. World Sci (1998) https:\/\/doi.org\/10.1142\/3903","DOI":"10.1142\/3903"},{"key":"10144_CR18","unstructured":"Jurafsky, D., Martin, J.H.: Speech and language processing, 2nd edn. Prentice Hall (2008)"},{"key":"10144_CR19","doi-asserted-by":"publisher","unstructured":"Kirsten, D.: The support of a recognizable series over a zero-sum free, commutative semiring is recognizable. Acta Cybernet. 20(2), 211\u2013221 (2011). https:\/\/doi.org\/10.14232\/actacyb.20.2.2011.1","DOI":"10.14232\/actacyb.20.2.2011.1"},{"key":"10144_CR20","doi-asserted-by":"publisher","unstructured":"Maletti, A., N\u00e1sz, A.T.: Weighted tree automata with constraints. In: V.\u00a0Diekert, M.\u00a0Volkov (eds.) Proc. 26th Int. Conf. Developments in Language Theory, pp. 226\u2013238. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-05578-2_18","DOI":"10.1007\/978-3-031-05578-2_18"},{"key":"10144_CR21","unstructured":"Maletti, A., N\u00e1sz, A.T., Paul, E.: Weighted HOM-problem for nonnegative integers. Tech. Rep. (2023) arXiv:2305.04117"},{"key":"10144_CR22","unstructured":"Mongy-Steen, J.: Transformation de noyaux reconnaissables d\u2019arbres\u2013for\u00eats RATEG. Ph.D. thesis, Universit\u00e9 de Lille (1981)"},{"key":"10144_CR23","doi-asserted-by":"crossref","unstructured":"N\u00e1sz, A.T.: Solving the weighted hom-problem with the help of unambiguity. In: Z.\u00a0Gazdag, S.\u00a0Iv\u00e1n (eds.) Proc. 16th Int. Conf. Automata and Formal Languages, EPTCS. Open Publishing Association (2023). To appear","DOI":"10.4204\/EPTCS.386.16"},{"key":"10144_CR24","doi-asserted-by":"publisher","unstructured":"Perrin, D.: Recent results on automata and infinite words. In: M.P. Chytil, V.\u00a0Koubek (eds.) Proc. 11th Int. Symp. Mathematical Foundations of Computer Science, LNCS, vol. 176, pp. 134\u2013148. Springer (1984). https:\/\/doi.org\/10.1007\/BFb0030294","DOI":"10.1007\/BFb0030294"},{"key":"10144_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6264-0","author":"A Salomaa","year":"1978","unstructured":"Salomaa, A., Soittola, M.: Automata-theoretic aspects of formal power series. Springer (1978). https:\/\/doi.org\/10.1007\/978-1-4612-6264-0","journal-title":"Springer"},{"issue":"2\u20133","key":"10144_CR26","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"MP Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.P.: On the definition of a family of automata. Inform. Control 4(2\u20133), 245\u2013270 (1961). https:\/\/doi.org\/10.1016\/S0019-9958(61)80020-X","journal-title":"Inform. Control"},{"issue":"4","key":"10144_CR27","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0022-0000(67)80022-9","volume":"1","author":"JW Thatcher","year":"1967","unstructured":"Thatcher, J.W.: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. J. Comput. Syst. Sci. 1(4), 317\u2013322 (1967). https:\/\/doi.org\/10.1016\/S0022-0000(67)80022-9","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10144_CR28","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"JW Thatcher","year":"1968","unstructured":"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\u201381 (1968). https:\/\/doi.org\/10.1007\/BF01691346","journal-title":"Math. Syst Theory"},{"key":"10144_CR29","doi-asserted-by":"publisher","unstructured":"Tison, S.: Tree automata, (dis-)equality constraints and term rewriting: What\u2019s new? In: M.\u00a0Schmidt-Schau\u00df (ed.) Proc. 22nd Int. Conf. Rewriting Techniques and Applications, LIPIcs, vol.\u00a010, pp. 1\u20132. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2011). https:\/\/doi.org\/10.4230\/LIPIcs.RTA.2011.1","DOI":"10.4230\/LIPIcs.RTA.2011.1"},{"issue":"3","key":"10144_CR30","first-page":"391","volume":"23","author":"H Wang","year":"1997","unstructured":"Wang, H.: On characters of semirings. Houston J. Math. 23(3), 391\u2013405 (1997)","journal-title":"Houston J. Math."},{"key":"10144_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17548-0","author":"R Wilhelm","year":"2012","unstructured":"Wilhelm, R., Seidl, H., Hack, S.: Compiler Design-Syntactic and Semantic Analysis. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-17548-0","journal-title":"Compiler Design-Syntactic and Semantic Analysis. Springer"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10144-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10144-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10144-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T11:03:37Z","timestamp":1706785417000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10144-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,3]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10144"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10144-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2023,10,3]]},"assertion":[{"value":"20 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}