{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T02:46:30Z","timestamp":1767494790920,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030625351"},{"type":"electronic","value":"9783030625368"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-62536-8_4","type":"book-chapter","created":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T02:02:50Z","timestamp":1604714570000},"page":"39-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monotonic Strong Bimonoids Is Decidable"],"prefix":"10.1007","author":[{"given":"Manfred","family":"Droste","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zolt\u00e1n","family":"F\u00fcl\u00f6p","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1vid","family":"K\u00f3sz\u00f3","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heiko","family":"Vogler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,6]]},"reference":[{"issue":"1","key":"4_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(87)90190-6","volume":"24","author":"A Alexandrakis","year":"1987","unstructured":"Alexandrakis, A., Bozapalidis, S.: Weighted grammars and Kleene\u2019s theorem. Inf. Process. Lett. 24(1), 1\u20134 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"4_CR2","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0304-3975(82)90019-6","volume":"18","author":"J Berstel","year":"1982","unstructured":"Berstel, J., Reutenauer, C.: Recognizable formal power series on trees. Theor. Comput. Sci. 18(2), 115\u2013148 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR3","unstructured":"Berstel, J., Reutenauer, C.: Rational Series and Their Languages. EATCS Monographs on Theoretical Computer Science, vol. 12. Springer, Heidelberg (1988)"},{"issue":"4","key":"4_CR4","first-page":"509","volume":"16","author":"B Borchardt","year":"2004","unstructured":"Borchardt, B.: A pumping lemma and decidability problems for recognizable tree series. Acta Cybern. 16(4), 509\u2013544 (2004)","journal-title":"Acta Cybern."},{"key":"4_CR5","first-page":"107","volume":"10","author":"B Borchardt","year":"2005","unstructured":"Borchardt, B., F\u00fcl\u00f6p, Z., Gazdag, Z., Maletti, A.: Bounds for tree automata with polynomial costs. J. Autom. Lang. Comb. 10, 107\u2013157 (2005)","journal-title":"J. Autom. Lang. Comb."},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"1560","DOI":"10.1016\/j.fss.2005.11.004","volume":"157","author":"B Borchardt","year":"2006","unstructured":"Borchardt, B., Maletti, A., \u0160e\u0161elja, B., Tepav\u010devic, A., Vogler, H.: Cut sets as recognizable tree languages. Fuzzy Sets Syst. 157, 1560\u20131571 (2006)","journal-title":"Fuzzy Sets Syst."},{"issue":"3","key":"4_CR7","first-page":"417","volume":"8","author":"B Borchardt","year":"2003","unstructured":"Borchardt, B., Vogler, H.: Determinization of finite state weighted tree automata. J. Autom. Lang. Comb. 8(3), 417\u2013463 (2003)","journal-title":"J. Autom. Lang. Comb."},{"issue":"3\/4","key":"4_CR8","first-page":"229","volume":"15","author":"M B\u00fcchse","year":"2010","unstructured":"B\u00fcchse, M., May, J., Vogler, H.: Determinization of weighted tree automata using factorizations. J. Autom. Lang. Comb. 15(3\/4), 229\u2013254 (2010)","journal-title":"J. Autom. Lang. Comb."},{"issue":"18","key":"4_CR9","doi-asserted-by":"publisher","first-page":"3479","DOI":"10.1016\/j.ins.2010.05.020","volume":"180","author":"M \u0106iri\u0107","year":"2010","unstructured":"\u0106iri\u0107, M., Droste, M., Ignjatovi\u0107, J., Vogler, H.: Determinization of weighted finite automata over strong bimonoids. Inf. Sci. 180(18), 3479\u20133520 (2010)","journal-title":"Inf. Sci."},{"key":"4_CR10","unstructured":"Comon, H., et al.: Tree automata techniques and applications (2008). http:\/\/tata.gforge.inria.fr"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-24897-9_2","volume-title":"Algebraic Foundations in Computer Science","author":"M Droste","year":"2011","unstructured":"Droste, M., G\u00f6tze, D., M\u00e4rcker, S., Meinecke, I.: Weighted tree automata over valuation monoids and their characterization by weighted logics. In: Kuich, W., Rahonis, G. (eds.) Algebraic Foundations in Computer Science. LNCS, vol. 7020, pp. 30\u201355. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-24897-9_2"},{"key":"4_CR12","series-title":"EATCS Monographs in Theoretical Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5","volume-title":"Handbook of Weighted Automata","year":"2009","unstructured":"Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.ic.2012.10.001","volume":"220\u2013221","author":"M Droste","year":"2012","unstructured":"Droste, M., Meinecke, I.: Weighted automata and weighted MSO logics for average and long-time behaviors. Inf. Comput. 220\u2013221, 44\u201359 (2012)","journal-title":"Inf. Comput."},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s00224-015-9658-9","volume":"59","author":"M Droste","year":"2016","unstructured":"Droste, M., Perevoshchikov, V.: Multi-weighted automata and MSO logic. Theory Comput. Syst. 59, 231\u2013261 (2016). https:\/\/doi.org\/10.1007\/s00224-015-9658-9","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"4_CR15","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/j.ins.2009.09.003","volume":"180","author":"M Droste","year":"2010","unstructured":"Droste, M., St\u00fcber, T., Vogler, H.: Weighted finite automata over strong bimonoids. Inf. Sci. 180(1), 156\u2013166 (2010)","journal-title":"Inf. Sci."},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2011.11.008","volume":"418","author":"M Droste","year":"2012","unstructured":"Droste, M., Vogler, H.: Weighted automata and multi-valued logics over arbitrary bounded lattices. Theor. Comput. Sci. 418, 14\u201336 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR17","unstructured":"Eilenberg, S.: Automata, Languages, and Machines - Volume A, Pure and Applied Mathematics, vol. 59. Academic Press, Cambridge (1974)"},{"key":"4_CR18","unstructured":"Engelfriet, J.: Tree automata and tree grammars. Technical report. DAIMI FN-10, Institute of Mathematics, University of Aarhus, Department of Computer Science, Denmark (1975). arXiv:1510.02036v1 [cs.FL], 7 October 2015"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"1450","DOI":"10.1016\/j.fss.2007.02.016","volume":"158","author":"Z \u00c9sik","year":"2007","unstructured":"\u00c9sik, Z., Liu, G.: Fuzzy tree automata. Fuzzy Sets Syst. 158, 1450\u20131460 (2007)","journal-title":"Fuzzy Sets Syst."},{"key":"4_CR20","unstructured":"F\u00fcl\u00f6p, Z., K\u00f3sz\u00f3, D., Vogler, H.: Crisp-determinization of weighted tree automata over strong bimonoids (2019). arXiv:1912.02660v1 [cs.FL], 5 December 2019"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s00224-007-9091-9","volume":"44","author":"Z F\u00fcl\u00f6p","year":"2009","unstructured":"F\u00fcl\u00f6p, Z., Maletti, A., Vogler, H.: A Kleene theorem for weighted tree automata over distributive multioperator monoids. Theory Comput. Syst. 44, 455\u2013499 (2009). https:\/\/doi.org\/10.1007\/s00224-007-9091-9","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"4_CR22","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/s00224-010-9296-1","volume":"50","author":"Z F\u00fcl\u00f6p","year":"2012","unstructured":"F\u00fcl\u00f6p, Z., St\u00fcber, T., Vogler, H.: A B\u00fcchi-like theorem for weighted tree automata over multioperator monoids. Theory Comput. Syst. 50(2), 241\u2013278 (2012). https:\/\/doi.org\/10.1007\/s00224-010-9296-1","journal-title":"Theory Comput. Syst."},{"key":"4_CR23","doi-asserted-by":"publisher","unstructured":"F\u00fcl\u00f6p, Z., Vogler, H.: Weighted tree automata and tree transducers. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. EATCS, pp. 313\u2013403. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_9","DOI":"10.1007\/978-3-642-01492-5_9"},{"key":"4_CR24","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree Automata. Akad\u00e9miai Kiad\u00f3, Budapest (1984). arXiv:1509.06233v1 [cs.FL], 21 September 2015"},{"key":"4_CR25","volume-title":"Introduction to Formal Language Theory","author":"M Harrison","year":"1978","unstructured":"Harrison, M.: Introduction to Formal Language Theory. Addison-Wesley, Boston (1978)"},{"key":"4_CR26","first-page":"287","volume":"10","author":"D Kirsten","year":"2005","unstructured":"Kirsten, D., M\u00e4urer, I.: On the determinization of weighted automata. J. Autom. Lang. Comb. 10, 287\u2013312 (2005)","journal-title":"J. Autom. Lang. Comb."},{"issue":"3","key":"4_CR27","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.tcs.2004.02.049","volume":"327","author":"I Klimann","year":"2004","unstructured":"Klimann, I., Lombardy, S., Mairesse, J., Prieur, C.: Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theor. Comput. Sci. 327(3), 349\u2013373 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR28","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.ipl.2018.08.005","volume":"140","author":"P Kostol\u00e1nyi","year":"2018","unstructured":"Kostol\u00e1nyi, P.: On deterministic weighted automata. Inf. Process. Lett. 140, 42\u201347 (2018)","journal-title":"Inf. Process. Lett."},{"key":"4_CR29","doi-asserted-by":"publisher","unstructured":"Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS Monographs in Theoretical Computer Science, vol. 5. Springer, Heidelberg (1986). https:\/\/doi.org\/10.1007\/978-3-642-69959-7_4","DOI":"10.1007\/978-3-642-69959-7_4"},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.tcs.2006.01.028","volume":"356","author":"S Lombardy","year":"2006","unstructured":"Lombardy, S., Sakarovitch, J.: Sequential? Theor. Comput. Sci. 356, 224\u2013244 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0304-3975(77)90001-9","volume":"5","author":"A Mandel","year":"1977","unstructured":"Mandel, A., Simon, I.: On finite semigroups of matrices. Theor. Comput. Sci. 5, 101\u2013111 (1977)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"4_CR32","first-page":"269","volume":"23","author":"M Mohri","year":"1997","unstructured":"Mohri, M.: Finite-state transducers in language and speech processing. Comput. Linguist. 23(2), 269\u2013311 (1997)","journal-title":"Comput. Linguist."},{"key":"4_CR33","unstructured":"Paul, E.: Finite sequentiality of unambiguous max-plus tree automata. In: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). vol. 126, pp. 53:1\u201353:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"3","key":"4_CR34","first-page":"89","volume":"40","author":"D Radovanovi\u0107","year":"2010","unstructured":"Radovanovi\u0107, D.: Weighted tree automata over strong bimonoids. Novi Sad J. Math. 40(3), 89\u2013108 (2010)","journal-title":"Novi Sad J. Math."},{"key":"4_CR35","series-title":"EATCS","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-642-01492-5_12","volume-title":"Handbook of Weighted Automata","author":"G Rahonis","year":"2009","unstructured":"Rahonis, G.: Fuzzy languages. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata. EATCS, pp. 481\u2013517. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5_12"},{"key":"4_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218","volume-title":"Elements of Automata Theory","author":"J Sakarovitch","year":"2009","unstructured":"Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009)"},{"key":"4_CR37","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"M Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.: On the definition of a family of automata. Inf. Control 4, 245\u2013270 (1961)","journal-title":"Inf. Control"},{"issue":"1","key":"4_CR38","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0304-3975(94)90271-2","volume":"126","author":"H Seidl","year":"1994","unstructured":"Seidl, H.: Finite tree automata with cost functions. Theor. Comput. Sci. 126(1), 113\u2013142 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR39","doi-asserted-by":"publisher","DOI":"10.1515\/9783112733356","volume-title":"The Concept of Fuzziness in Automata and Language Theory","author":"W Wechler","year":"1978","unstructured":"Wechler, W.: The Concept of Fuzziness in Automata and Language Theory, 5th edn. Studien zur Algebra und ihre Anwendungen, Akademie-Verlag, Berlin (1978)","edition":"5"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-62536-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T19:22:44Z","timestamp":1741634564000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-62536-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030625351","9783030625368"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-62536-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"6 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DCFS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Descriptional Complexity of Formal Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 August 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/sofl2020.conf.tuwien.ac.at\/DCFS2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}