{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:09:51Z","timestamp":1742976591601,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531310"},{"type":"electronic","value":"9783662531327"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53132-7_30","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T21:25:06Z","timestamp":1468963506000},"page":"368-379","source":"Crossref","is-referenced-by-count":4,"title":["On Finite and Polynomial Ambiguity of Weighted Tree Automata"],"prefix":"10.1007","author":[{"given":"Erik","family":"Paul","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,21]]},"reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-3-540-85780-8_8","volume-title":"Developments in Language Theory","author":"C Allauzen","year":"2008","unstructured":"Allauzen, C., Mohri, M., Rastogi, A.: General algorithms for testing the ambiguity of finite automata. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 108\u2013120. Springer, Heidelberg (2008)"},{"issue":"2","key":"30_CR2","doi-asserted-by":"crossref","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":"30_CR3","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-73235-5","volume-title":"Rational Series and Their Languages","author":"J Berstel","year":"1988","unstructured":"Berstel, J., Reutenauer, C.: Rational Series and Their Languages. Monographs in Theoretical Computer Science. An EATCS Series, vol. 12. Springer, Heidelberg (1988)"},{"issue":"4","key":"30_CR4","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF01893886","volume":"28","author":"S Bozapalidis","year":"1991","unstructured":"Bozapalidis, S.: Effective construction of the syntactic algebra of a recognizable series on trees. Acta Informatica 28(4), 351\u2013363 (1991)","journal-title":"Acta Informatica"},{"key":"30_CR5","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.: Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundl. Math. 6, 66\u201392 (1960)","journal-title":"Z. Math. Logik und Grundl. Math."},{"key":"30_CR6","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007). http:\/\/www.grappa.univ-lille3.fr\/tata"},{"issue":"5","key":"30_CR7","doi-asserted-by":"crossref","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. Syst. Sci. 4(5), 406\u2013451 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"30_CR8","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.tcs.2007.02.055","volume":"380","author":"M Droste","year":"2007","unstructured":"Droste, M., Gastin, P.: Weighted automata and weighted logics. Theor. Comput. Sci. 380(1\u20132), 69\u201386 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR9","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","volume-title":"Handbook of Weighted Automata","year":"2009","unstructured":"Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2009)"},{"issue":"3","key":"30_CR10","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/j.tcs.2006.08.025","volume":"366","author":"M Droste","year":"2006","unstructured":"Droste, M., Vogler, H.: Weighted tree automata and weighted logics. Theor. Comput. Sci. 366(3), 228\u2013247 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C Elgot","year":"1961","unstructured":"Elgot, C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98, 21\u201352 (1961)","journal-title":"Trans. Am. Math. Soc."},{"key":"30_CR12","series-title":"Monographs in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-3-642-01492-5_9","volume-title":"Handbook of Weighted Automata","author":"Z F\u00fcl\u00f6p","year":"2009","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. Monographs in Theoretical Computer Science. An EATCS Series, pp. 313\u2013403. Springer, Heidelberg (2009)"},{"key":"30_CR13","first-page":"23","volume":"960","author":"K Hashiguchi","year":"1996","unstructured":"Hashiguchi, K., Ishiguro, K.: Decidability of the equivalence problem for finitely ambiguous finance automata. Surikaisekikenkyusho Kokyuroku 960, 23\u201336 (1996)","journal-title":"Surikaisekikenkyusho Kokyuroku"},{"issue":"3","key":"30_CR14","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1051\/ita:2008017","volume":"42","author":"D Kirsten","year":"2008","unstructured":"Kirsten, D.: A Burnside approach to the termination of Mohri\u2019s algorithm for polynomially ambiguous min-plus-automata. RAIRO-Inf. Theor. Appl. 42(3), 553\u2013581 (2008)","journal-title":"RAIRO-Inf. Theor. Appl."},{"issue":"3","key":"30_CR15","doi-asserted-by":"crossref","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":"30_CR16","doi-asserted-by":"crossref","unstructured":"Kreutzer, S., Riveros, C.: Quantitative monadic second-order logic. In: 28th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS, pp. 113\u2013122. IEEE Computer Society (2013)","DOI":"10.1109\/LICS.2013.16"},{"issue":"03","key":"30_CR17","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1142\/S0218196794000063","volume":"04","author":"D Krob","year":"1994","unstructured":"Krob, D.: The equality problem for rational series with multiplicities in the tropical semiring is undecidable. Int. J. Algebra Comput. 04(03), 405\u2013425 (1994)","journal-title":"Int. J. Algebra Comput."},{"key":"30_CR18","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69959-7","volume-title":"Semirings, Automata, Languages","author":"W Kuich","year":"1986","unstructured":"Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer Science, vol. 5. Springer, Heidelberg (1986)"},{"issue":"4","key":"30_CR19","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1142\/S012905410500325X","volume":"16","author":"A Maletti","year":"2005","unstructured":"Maletti, A.: Relating tree series transducers and weighted tree automata. Int. J. Found. Comput. Sci. 16(4), 723\u2013741 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"30_CR20","first-page":"455","volume":"12","author":"G Rahonis","year":"2007","unstructured":"Rahonis, G.: Weighted Muller tree automata and weighted logics. J. Autom. Lang. Comb. 12(4), 455\u2013483 (2007)","journal-title":"J. Autom. Lang. Comb."},{"key":"30_CR21","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-Theoretic Aspects of Formal Power Series","author":"A Salomaa","year":"1978","unstructured":"Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, New York (1978)"},{"issue":"2\u20133","key":"30_CR22","doi-asserted-by":"crossref","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(2\u20133), 245\u2013270 (1961)","journal-title":"Inf. Control"},{"issue":"6","key":"30_CR23","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/BF00263578","volume":"26","author":"H Seidl","year":"1989","unstructured":"Seidl, H.: On the finite degree of ambiguity of finite tree automata. Acta Informatica 26(6), 527\u2013542 (1989)","journal-title":"Acta Informatica"},{"issue":"2","key":"30_CR24","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"H Seidl","year":"1991","unstructured":"Seidl, H., Weber, A.: On the degree of ambiguity of finite automata. Theor. Comput. Sci. 88(2), 325\u2013349 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"30_CR25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J Thatcher","year":"1968","unstructured":"Thatcher, J., Wright, J.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theor. 2(1), 57\u201381 (1968)","journal-title":"Math. Syst. Theor."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53132-7_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T14:45:57Z","timestamp":1498315557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53132-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531310","9783662531327"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53132-7_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}