{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:28:51Z","timestamp":1725701331182},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642329425"},{"type":"electronic","value":"9783642329432"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32943-2_18","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T04:59:35Z","timestamp":1346129975000},"page":"228-242","source":"Crossref","is-referenced-by-count":2,"title":["Approximate Verification and Enumeration Problems"],"prefix":"10.1007","author":[{"given":"Sylvain","family":"Peyronnet","sequence":"first","affiliation":[]},{"given":"Michel","family":"De Rougemont","sequence":"additional","affiliation":[]},{"given":"Yann","family":"Strozecki","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/3-540-61474-5_57","volume-title":"Computer Aided Verification","author":"C. Baier","year":"1996","unstructured":"Baier, C.: Polynomial Time Algorithms for Testing Probabilistic Bisimulation and Simulation. In: Alur, R., Henzinger, T.A. (eds.) CAV 1996. LNCS, vol.\u00a01102, pp. 38\u201349. Springer, Heidelberg (1996)"},{"issue":"2","key":"18_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00454-002-2756-x","volume":"28","author":"A. Brieden","year":"2002","unstructured":"Brieden, A.: Geometric optimization problems likely not contained in apx. Discrete and Computational Geometry\u00a028(2), 201\u2013209 (2002)","journal-title":"Discrete and Computational Geometry"},{"key":"18_CR3","unstructured":"Broder, A.: On the resemblance and containment of documents. In: SEQUENCES 1997: Proceedings of the Compression and Complexity of Sequences (1997)"},{"key":"18_CR4","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 667\u2013676. Society for Industrial and Applied Mathematics (2002)"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"de Rougemont, M., Tracol, M.: Statistic analysis for probabilistic processes. In: Proc. of the 24th Annual IEEE Symposium on Logic in Computer Science (LICS), pp. 299\u2013308. IEEE Computer Society (2009)","DOI":"10.1109\/LICS.2009.36"},{"key":"18_CR6","volume-title":"Finite State Markovian Decision Processes","author":"C. Derman","year":"1970","unstructured":"Derman, C.: Finite State Markovian Decision Processes. Academic Press, Inc., Orlando (1970)"},{"issue":"3","key":"18_CR7","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.tcs.2003.09.013","volume":"318","author":"J. Desharnais","year":"2004","unstructured":"Desharnais, J., Gupta, V., Jagadeesan, R., Panangaden, P.: Metrics for labelled Markov processes. Theoretical Computer Science\u00a0318(3), 323\u2013354 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"18_CR8","doi-asserted-by":"publisher","first-page":"2251","DOI":"10.1137\/070703776","volume":"39","author":"E. Fischer","year":"2010","unstructured":"Fischer, E., Magniez, F., de Rougemont, M.: Approximate satisfiability and equivalence. SIAM J. Comput.\u00a039(6), 2251\u20132281 (2010)","journal-title":"SIAM J. Comput."},{"key":"18_CR9","first-page":"136","volume":"18","author":"E. Gat","year":"2011","unstructured":"Gat, E., Goldwasser, S.: Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 136 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1017\/S0963548306007504","volume":"15","author":"R. Kannan","year":"2006","unstructured":"Kannan, R., Lov\u00e1sz, L., Montenegro, R.: Blocking conductance and mixing in random walks. Comb. Probab. Comput.\u00a015, 541\u2013570 (2006)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X","volume":"11","author":"R. Kannan","year":"1997","unstructured":"Kannan, R., Lov\u00e1sz, L., Simonovits, M.: Random walks and an o*(n5) volume algorithm for convex bodies. Random Structures and Algorithms\u00a011(1), 1\u201350 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR12","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":"18_CR13","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1145\/380752.380801","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing","author":"A.R. Klivans","year":"2001","unstructured":"Klivans, A.R., Spielman, D.: Randomness efficient identity testing of multivariate polynomials. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 216\u2013223. ACM, New York (2001)"},{"issue":"4","key":"18_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.3240040402","volume":"4","author":"L. Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L., Simonovits, M.: Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms\u00a04(4), 359\u2013412 (1993)","journal-title":"Random Structures & Algorithms"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1214\/aop\/1176990729","volume":"18","author":"D. Ornstein","year":"1990","unstructured":"Ornstein, D., Weiss, B.: How sampling reveals a process. Annals of Probability\u00a018, 905\u2013930 (1990)","journal-title":"Annals of Probability"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons (1994)","DOI":"10.1002\/9780470316887"},{"issue":"3","key":"18_CR17","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":"4","key":"18_CR18","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM)\u00a027(4), 717 (1980)","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"18_CR19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s10107-003-0447-x","volume":"97","author":"M. Simonovits","year":"2003","unstructured":"Simonovits, M.: How to compute the volume in high dimension? Mathematical Programming\u00a097(1), 337\u2013374 (2003)","journal-title":"Mathematical Programming"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/978-3-642-15155-2_55","volume-title":"Mathematical Foundations of Computer Science 2010","author":"Y. Strozecki","year":"2010","unstructured":"Strozecki, Y.: Enumeration of the Monomials of a Polynomial and Related Complexity Classes. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 629\u2013640. Springer, Heidelberg (2010)"},{"key":"18_CR21","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 Journal on Computing\u00a021, 216 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic Algorithms for Sparse Polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32943-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T05:51:33Z","timestamp":1557208293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32943-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642329425","9783642329432"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32943-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}