{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:06:36Z","timestamp":1767236796555,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662466773"},{"type":"electronic","value":"9783662466780"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46678-0_19","type":"book-chapter","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T09:42:21Z","timestamp":1427881341000},"page":"297-311","source":"Crossref","is-referenced-by-count":2,"title":["Minimisation of Multiplicity Tree Automata"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kiefer","sequence":"first","affiliation":[]},{"given":"Ines","family":"Marusic","sequence":"additional","affiliation":[]},{"given":"James","family":"Worrell","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"19_CR1","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. Theoretical Computer Science\u00a018(2), 115\u2013148 (1982)","journal-title":"Theoretical Computer Science"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer (1997)","DOI":"10.1007\/978-1-4612-0701-6"},{"issue":"4","key":"19_CR3","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.\u00a016(4), 509\u2013544 (2004)","journal-title":"Acta Cybern."},{"issue":"4","key":"19_CR4","doi-asserted-by":"publisher","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 Inf.\u00a028(4), 351\u2013363 (1991)","journal-title":"Acta Inf."},{"issue":"4","key":"19_CR5","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1051\/ita\/1989230404491","volume":"23","author":"S. Bozapalidis","year":"1989","unstructured":"Bozapalidis, S., Alexandrakis, A.: Repr\u00e9sentations matricielles des s\u00e9ries d\u2019arbre reconnaissables. RAIRO-Theoretical Informatics and Applications-Informatique Th\u00e9orique et Applications\u00a023(4), 449\u2013459 (1989)","journal-title":"RAIRO-Theoretical Informatics and Applications-Informatique Th\u00e9orique et Applications"},{"issue":"1","key":"19_CR6","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0304-3975(83)90100-7","volume":"27","author":"S. Bozapalidis","year":"1983","unstructured":"Bozapalidis, S., Louscou-Bozapalidou, O.: The rank of a formal tree power series. Theoretical Computer Science\u00a027(1), 211\u2013215 (1983)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"19_CR7","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1016\/S0019-9958(68)90917-0","volume":"13","author":"W.S. Brainerd","year":"1968","unstructured":"Brainerd, W.S.: The minimalization of tree automata. Information and Control\u00a013(5), 484\u2013491 (1968)","journal-title":"Information and Control"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proceedings of STOC 1988, pp. 460\u2013467. ACM (1988)","DOI":"10.1145\/62212.62257"},{"issue":"1","key":"19_CR9","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/S0022-0000(71)80005-3","volume":"5","author":"J.W. Carlyle","year":"1971","unstructured":"Carlyle, J.W., Paz, A.: Realizations by stochastic finite automata. Journal of Computer and System Sciences\u00a05(1), 26\u201340 (1971)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-45007-6_13","volume-title":"Developments in Language Theory","author":"J. Carme","year":"2003","unstructured":"Carme, J., Gilleron, R., Lemay, A., Terlutte, A., Tommasi, M.: Residual finite tree automata. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) DLT 2003. LNCS, vol.\u00a02710, pp. 171\u2013182. Springer, Heidelberg (2003)"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-540-76336-9_13","volume-title":"Implementation and Application of Automata","author":"R.C. Carrasco","year":"2007","unstructured":"Carrasco, R.C., Daciuk, J., Forcada, M.L.: An implementation of deterministic tree automata minimization. In: Holub, J., \u017d\u010f\u00e1rek, J. (eds.) CIAA 2007. LNCS, vol.\u00a04783, pp. 122\u2013129. Springer, Heidelberg (2007)"},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(92)90002-W","volume":"97","author":"S. Cho","year":"1992","unstructured":"Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inf. Comput.\u00a097(1), 1\u201322 (1992)","journal-title":"Inf. Comput."},{"issue":"1-3","key":"19_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Information and Control\u00a064(1-3), 2\u201322 (1985)","journal-title":"Information and Control"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/11812128_14","volume-title":"Implementation and Application of Automata","author":"C. Cortes","year":"2006","unstructured":"Cortes, C., Mohri, M., Rastogi, A.: On the computation of some standard distances between probabilistic automata. In: Ibarra, O.H., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol.\u00a04094, pp. 137\u2013149. Springer, Heidelberg (2006)"},{"issue":"4","key":"19_CR15","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L. Csanky","year":"1976","unstructured":"Csanky, L.: Fast parallel matrix inversion algorithms. SIAM J. Comput.\u00a05(4), 618\u2013623 (1976)","journal-title":"SIAM J. Comput."},{"key":"19_CR16","first-page":"197","volume":"53","author":"M. Fliess","year":"1974","unstructured":"Fliess, M.: Matrices de Hankel. Journal de Math\u00e9matiques Pures et Appliqu\u00e9es\u00a053, 197\u2013222 (1974)","journal-title":"Journal de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"issue":"3","key":"19_CR17","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E.M. Gold","year":"1978","unstructured":"Gold, E.M.: Complexity of automaton identification from given data. Information and Control\u00a037(3), 302\u2013320 (1978)","journal-title":"Information and Control"},{"key":"19_CR18","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/11872436_22","volume-title":"Grammatical Inference: Algorithms and Applications","author":"A. Habrard","year":"2006","unstructured":"Habrard, A., Oncina, J.: Learning multiplicity tree automata. In: Sakakibara, Y., Kobayashi, S., Sato, K., Nishino, T., Tomita, E. (eds.) ICGI 2006. LNCS (LNAI), vol.\u00a04201, pp. 268\u2013280. Springer, Heidelberg (2006)"},{"issue":"4\/5","key":"19_CR19","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/0020-0190(80)90042-3","volume":"11","author":"O.H. Ibarra","year":"1980","unstructured":"Ibarra, O.H., Moran, S., Rosier, L.E.: A note on the parallel complexity of computing the rank of order n matrices. Information Processing Letters\u00a011(4\/5), 162 (1980)","journal-title":"Information Processing Letters"},{"issue":"6","key":"19_CR20","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput.\u00a022(6), 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"19_CR21","unstructured":"Kiefer, S., Marusic, I., Worrell, J.: Minimisation of multiplicity tree automata. Technical report, arxiv.org (2014), \n                      \n                        http:\/\/arxiv.org\/abs\/1410.535"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Kiefer, S., Murawski, A., Ouaknine, J., Wachter, B., Worrell, J.: On the complexity of equivalence and minimisation for \u211a-weighted automata. Logical Methods in Computer Science 9(1) (2013)","DOI":"10.2168\/LMCS-9(1:8)2013"},{"issue":"11","key":"19_CR23","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1016\/j.ic.2009.01.004","volume":"207","author":"A. Maletti","year":"2009","unstructured":"Maletti, A.: Minimizing deterministic weighted tree automata. Inf. Comput.\u00a0207(11), 1284\u20131299 (2009)","journal-title":"Inf. Comput."},{"key":"19_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-662-44522-8_35","volume-title":"Mathematical Foundations of Computer Science 2014","author":"I. Marusic","year":"2014","unstructured":"Marusic, I., Worrell, J.: Complexity of equivalence and learning for multiplicity tree automata. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part I. LNCS, vol.\u00a08634, pp. 414\u2013425. Springer, Heidelberg (2014)"},{"issue":"2-3","key":"19_CR25","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"M.P. Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.P.: On the definition of a family of automata. Information and Control\u00a04(2-3), 245\u2013270 (1961)","journal-title":"Information and Control"},{"issue":"3","key":"19_CR26","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1137\/0219027","volume":"19","author":"H. Seidl","year":"1990","unstructured":"Seidl, H.: Deciding equivalence of finite tree automata. SIAM J. Comput.\u00a019(3), 424\u2013437 (1990)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"19_CR27","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0221017","volume":"21","author":"W.-G. Tzeng","year":"1992","unstructured":"Tzeng, W.-G.: A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput.\u00a021(2), 216\u2013227 (1992)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46678-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T14:23:49Z","timestamp":1559139829000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46678-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662466773","9783662466780"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46678-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}