{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:31Z","timestamp":1778498011179,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439500","type":"print"},{"value":"9783662439517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_23","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T04:37:49Z","timestamp":1402461469000},"page":"268-279","source":"Crossref","is-referenced-by-count":2,"title":["Stability and Complexity of Minimising Probabilistic Automata"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kiefer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bj\u00f6rn","family":"Wachter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/0890-5401(89)90049-7","volume":"83","author":"A. Aggarwal","year":"1989","unstructured":"Aggarwal, A., Booth, H., O\u2019Rourke, J., Suri, S., Yap, C.K.: Finding minimal convex nested polygons. Information and Computation\u00a083(1), 98\u2013110 (1989)","journal-title":"Information and Computation"},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1090\/qam\/42792","volume":"9","author":"W.E. Arnoldi","year":"1951","unstructured":"Arnoldi, W.E.: The principle of minimized iteration in the solution of the matrix eigenvalue problem. Quarterly of Applied Mathematics\u00a09, 17\u201329 (1951)","journal-title":"Quarterly of Applied Mathematics"},{"issue":"3","key":"23_CR3","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/337244.337257","volume":"47","author":"A. Beimel","year":"2000","unstructured":"Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. Journal of the ACM\u00a047(3), 506\u2013530 (2000)","journal-title":"Journal of the ACM"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Berstel, J., Reutenauer, C.: Rational Series and Their Languages. Springer (1988)","DOI":"10.1007\/978-3-642-73235-5"},{"key":"23_CR5","unstructured":"Bonchi, F., Bonsangue, M.M., Hansen, H.H., Panangaden, P., Rutten, J.J.M.M., Silva, A.: Algebra-coalgebra duality in Brzozowski\u2019s minimization algorithm. ACM Transactions on Computational Logic (to appear)"},{"key":"23_CR6","series-title":"MRI Symposia Series","first-page":"529","volume-title":"Symposium on Mathematical Theory of Automata","author":"J.A. Brzozowski","year":"1962","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Symposium on Mathematical Theory of Automata. MRI Symposia Series, vol.\u00a012, pp. 529\u2013561. Polytechnic Press, Polytechnic Institute of Brooklyn (1962)"},{"issue":"3","key":"23_CR7","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF01088986","volume":"13","author":"R.G. Bukharaev","year":"1980","unstructured":"Bukharaev, R.G.: Probabilistic automata. Journal of Soviet Mathematics\u00a013(3), 359\u2013386 (1980)","journal-title":"Journal of Soviet Mathematics"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proceedings of STOC 1988, pp. 460\u2013467 (1988)","DOI":"10.1145\/62212.62257"},{"issue":"1","key":"23_CR9","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. Information and Computation\u00a097(1), 1\u201322 (1992)","journal-title":"Information and Computation"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/3-540-60220-8_52","volume-title":"Algorithms and Data Structures","author":"G. Das","year":"1995","unstructured":"Das, G., Goodrich, M.T.: On the complexity of approximating and illuminating three-dimensional convex polyhedra. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 74\u201385. Springer, Heidelberg (1995)"},{"issue":"1","key":"23_CR11","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0304-3975(92)90088-W","volume":"103","author":"G. Das","year":"1992","unstructured":"Das, G., Joseph, D.: Minimum vertex hulls for polyhedral domains. Theoretical Computer Science\u00a0103(1), 107\u2013135 (1992)","journal-title":"Theoretical Computer Science"},{"key":"23_CR12","unstructured":"Golub, G.H., van Loan, C.F.: Matrix Computations. John Hopkins University Press (1989)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM (2002)","DOI":"10.1137\/1.9780898718027"},{"issue":"4","key":"23_CR14","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1145\/320941.320947","volume":"5","author":"A.S. Householder","year":"1958","unstructured":"Householder, A.S.: Unitary triangularization of a nonsymmetric matrix. Journal of the ACM\u00a05(4), 339\u2013342 (1958)","journal-title":"Journal of the ACM"},{"issue":"3","key":"23_CR15","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0097-8493(93)90079-O","volume":"17","author":"K. Culik II","year":"1993","unstructured":"Culik II, K., Kari, J.: Image compression using weighted finite automata. Computers & Graphics\u00a017(3), 305\u2013313 (1993)","journal-title":"Computers & Graphics"},{"issue":"6","key":"23_CR16","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 Journal on Computing\u00a022(6), 1117\u20131141 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/978-3-642-22110-1_42","volume-title":"Computer Aided Verification","author":"S. Kiefer","year":"2011","unstructured":"Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J.: Language\u00a0equivalence\u00a0for probabilistic\u00a0automata. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol.\u00a06806, pp. 526\u2013540. Springer, Heidelberg (2011)"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J.: On the complexity of equivalence and minimisation for Q-weighted automata. Logical Methods in Computer Science 9(1:8), 1\u201322 (2013)","DOI":"10.2168\/LMCS-9(1:8)2013"},{"key":"23_CR19","unstructured":"Kiefer, S., Wachter, B.: Stability and complexity of minimising probabilistic automata. Technical report, arxiv.org (2014), \n                    \n                      http:\/\/arxiv.org\/abs\/1404.6673"},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.ic.2012.07.002","volume":"218","author":"P. Mateus","year":"2012","unstructured":"Mateus, P., Qiu, D., Li, L.: On the complexity of minimizing probabilistic and quantum automata. Information and Computation\u00a0218, 36\u201353 (2012)","journal-title":"Information and Computation"},{"key":"23_CR21","unstructured":"Mitchell, J.S.B., Suri, S.: Separation and approximation of polyhedral objects. In: Proceedings of SODA, pp. 296\u2013306 (1992)"},{"key":"23_CR22","unstructured":"Paz, A.: Introduction to probabilistic automata. Academic Press (1971)"},{"issue":"3","key":"23_CR23","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Information and Control\u00a06(3), 230\u2013245 (1963)","journal-title":"Information and Control"},{"issue":"3","key":"23_CR24","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. Parts I\u2013III. Journal of Symbolic Computation\u00a013(3), 255\u2013352 (1992)","journal-title":"Journal of Symbolic Computation"},{"key":"23_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, 245\u2013270 (1961)","journal-title":"Information and Control"},{"issue":"2","key":"23_CR26","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TC.1979.1675300","volume":"C-28","author":"C.B. Silio","year":"1979","unstructured":"Silio, C.B.: An efficient simplex coverability algorithm in E\n                  2 with application to stochastic sequential machines. IEEE Transactions on Computers\u00a0C-28(2), 109\u2013120 (1979)","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:31:32Z","timestamp":1558909892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}