{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T13:56:58Z","timestamp":1725803818177},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319106953"},{"type":"electronic","value":"9783319106960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-10696-0_26","type":"book-chapter","created":{"date-parts":[[2014,8,27]],"date-time":"2014-08-27T14:33:45Z","timestamp":1409150025000},"page":"329-344","source":"Crossref","is-referenced-by-count":1,"title":["Decidable Problems for Unary PFAs"],"prefix":"10.1007","author":[{"given":"Rohit","family":"Chadha","sequence":"first","affiliation":[]},{"given":"Dileep","family":"Kini","sequence":"additional","affiliation":[]},{"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Akshay, S., Genest, B., Thiagarajan, P.S.: Approximate verification of the symbolic dynamics of markov chains. In: LICS, pp. 55\u201364 (2012)","DOI":"10.1109\/LICS.2012.17"},{"issue":"5","key":"26_CR2","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E. Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Bro Miltersen, P.: On the complexity of numerical analysis. SIAM J. Comput.\u00a038(5), 1987\u20132006 (2009)","journal-title":"SIAM J. Comput."},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-662-40087-6_6","volume-title":"GI - 4. Jahrestagung","author":"A. Bertoni","year":"1975","unstructured":"Bertoni, A.: The solution of problems relative to probabilistic automata in the frame of formal language theory. In: Siefkes, D. (ed.) GI 1974. LNCS, vol.\u00a026, pp. 107\u2013112. Springer, Heidelberg (1975)"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-642-40313-2_24","volume-title":"Mathematical Foundations of Computer Science 2013","author":"R. Chadha","year":"2013","unstructured":"Chadha, R., Sistla, A.P., Viswanathan, M.: Probabilistic automata with isolated cut-points. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 254\u2013265. Springer, Heidelberg (2013)"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs (extended abstract). In: 30th Annual Symposium on Foundations of Computer Science, pp. 462\u2013467 (1989)","DOI":"10.1109\/SFCS.1989.63519"},{"issue":"3","key":"26_CR7","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1142\/S0129054108005814","volume":"19","author":"L. Doyen","year":"2008","unstructured":"Doyen, L., Henzinger, T.A., Raskin, J.-F.: Equivalence of labeled markov chains. Inernational Journal of Foundations of Computer Science\u00a019(3), 549\u2013563 (2008)","journal-title":"Inernational Journal of Foundations of Computer Science"},{"key":"26_CR8","unstructured":"Gantmacher, F.R.: Applications of the Theory of Matrices. Dover Books on Mathematics Series, Dover (2005)"},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/978-3-642-14162-1_44","volume-title":"Automata, Languages and Programming","author":"H. Gimbert","year":"2010","unstructured":"Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: Decidable and undecidable problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06199, pp. 527\u2013538. Springer, Heidelberg (2010)"},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/978-3-540-45138-9_40","volume-title":"Mathematical Foundations of Computer Science 2003","author":"G. Gramlich","year":"2003","unstructured":"Gramlich, G.: Probabilistic and nondeterministic unary automata. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 460\u2013469. Springer, Heidelberg (2003)"},{"key":"26_CR11","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":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-642-28729-9_31","volume-title":"Foundations of Software Science and Computational Structures","author":"S. Kiefer","year":"2012","unstructured":"Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J.: On the complexity of the equivalence problem for probabilistic automata. In: Birkedal, L. (ed.) FOSSACS 2012. LNCS, vol.\u00a07213, pp. 467\u2013481. Springer, Heidelberg (2012)"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Korthikanti, V.A., Viswanathan, M., Agha, G., Kwon, Y.: Reasoning about mdps as transformers of probability distributions. In: QEST, pp. 199\u2013208 (2010)","DOI":"10.1109\/QEST.2010.35"},{"key":"26_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-30482-1_21","volume-title":"Formal Methods and Software Engineering","author":"Y. Kwon","year":"2004","unstructured":"Kwon, Y., Agha, G.: Linear Inequality LTL (iLTL): A Model Checker for Discrete Time Markov Chains. In: Davies, J., Schulte, W., Barnett, M. (eds.) ICFEM 2004. LNCS, vol.\u00a03308, pp. 194\u2013208. Springer, Heidelberg (2004)"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Kwon, Y.M., Agha, G.: A Markov Reward Model for Software Reliability. In: IEEE International Parallel and Distributed Processing Symposium, IPDPS 2007, pp. 1\u20136 (2007)","DOI":"10.1109\/IPDPS.2007.370525"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Norris, J.R.: Markov Chains. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511810633"},{"key":"26_CR17","unstructured":"Paz, A.: Introduction to probabilistic automata. Academic Press (1971)"},{"issue":"3","key":"26_CR18","first-page":"230","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Information and Computation\u00a06(3), 230\u2013245 (1963)","journal-title":"Information and Computation"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Rutten, J.M., Kwiatkowska, M., Norman, G., Parker, D.: Mathematical Techniques for Analyzing Concurrent and Probabilistic Systems. AMS (2004)","DOI":"10.1090\/crmm\/023"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Salomaa, A., Soittola, M., Bauer, F.L., Gries, D.: Automata-theoretic aspects of formal power series. Texts and monographs in computer science. Springer (1978)","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/3-540-09510-1_42","volume-title":"Automata, Languages, and Programming","author":"A. Sch\u00f6nhage","year":"1979","unstructured":"Sch\u00f6nhage, A.: On the power of random access machines. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol.\u00a071, pp. 520\u2013529. Springer, Heidelberg (1979)"},{"issue":"2-3","key":"26_CR22","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"},{"key":"26_CR23","unstructured":"Senata, E.: Non-negative Matrices and Markov Chains. George Allen & Unwin Ltd. (1973)"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: Proc. of the 5th Ann. ACM Symposium on Theory of Computing, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"issue":"4","key":"26_CR25","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/S0019-9958(68)90360-4","volume":"12","author":"P. Turakainen","year":"1968","unstructured":"Turakainen, P.: On stochastic languages. Information and Control\u00a012(4), 304\u2013313 (1968)","journal-title":"Information and Control"},{"issue":"2","key":"26_CR26","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."},{"issue":"3","key":"26_CR27","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(86)90141-6","volume":"47","author":"K.W. Wagner","year":"1986","unstructured":"Wagner, K.W.: Some observations on the connection between counting and recursion. Theoretical Computer Science\u00a047(3), 131\u2013147 (1986)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Quantitative Evaluation of Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-10696-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T17:56:48Z","timestamp":1558979808000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-10696-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319106953","9783319106960"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-10696-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}