乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:29Z","timestamp":1725665069638},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_16","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:22:12Z","timestamp":1330280532000},"page":"187-195","source":"Crossref","is-referenced-by-count":12,"title":["Tally languages accepted by Monte Carlo pushdown automata"],"prefix":"10.1007","author":[{"given":"J\u0101nis","family":"Ka\u0146eps","sequence":"first","affiliation":[]},{"given":"Dainis","family":"Geidmanis","sequence":"additional","affiliation":[]},{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"A.AMBAINIS, The complexity of probabilistic versus deterministic finite automata. Lecture Notes in Computer Science, 1178(1996).","DOI":"10.1007\/BFb0009499"},{"key":"16_CR2","first-page":"201","volume":"233","author":"R. Freivalds","year":"1975","unstructured":"R. FREIVALDS, Fast computation by probabilistic Turing machines. Proceedings of Latvian State University, 233 (1975), 201\u2013205 (in Russian).","journal-title":"Proceedings of Latvian State University"},{"key":"16_CR3","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-09526-8_5","volume":"74","author":"R. Freivalds","year":"1979","unstructured":"R. FREIVALDS, Fast probabilistic algorithms. Lecture Notes in Computer Science, 74 (1979), 57\u201369.","journal-title":"Lecture Notes in Computer Science"},{"key":"16_CR4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(81)90057-0","volume":"13","author":"R. Freivalds","year":"1981","unstructured":"R. FREIVALDS, Projections of languages recognizable by probabilistic and alternating finite multitape automata. Information Processing Letters, V. 13, 1981, 195\u2013198.","journal-title":"Information Processing Letters"},{"key":"16_CR5","unstructured":"R.FREIVALDS, Capabilities of different models of 1-way probabilistic automata. Izvestija VUZ, Matematika, No.5 (228), 1981, 26\u201334 (in Russian)."},{"key":"16_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-10856-4_72","volume":"118","author":"R. Freivalds","year":"1981","unstructured":"R. FREIVALDS, Probabilistic two-way machines. Lecture Notes in Computer Science, 118(1981), 33\u201345.","journal-title":"Lecture Notes in Computer Science"},{"key":"16_CR7","unstructured":"R. FREIVALDS, On the growth of the number of states in result of determinization of probabilistic finite automata, Avtomatika i Vi\u010dislitelnaja Tehnika, 1982, N.3, 39\u201342 (in Russian)"},{"key":"16_CR8","first-page":"39","volume":"24","author":"R. Freivalds","year":"1985","unstructured":"R. FREIVALDS, Space and reversal complexity of probabilistic one-way Turing machines. Annals of Discrete Mathematics, 24 (1985), 39\u201350.","journal-title":"Annals of Discrete Mathematics"},{"key":"16_CR9","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1007\/3-540-58201-0_100","volume":"820","author":"R. Freivalds","year":"1994","unstructured":"R. FREIVALDS, M. KARPINSKI, Lower space bounds for randomized computation. Lecture Notes in Computer Science, 820 (1994), 580\u2013592.","journal-title":"Lecture Notes in Computer Science"},{"key":"16_CR10","unstructured":"N. Z. GABBASOV, T. A. MURTAZINA, Improving the estimate of Rabin's reduction theorem, Algorithms and Automata, Kazan University, 1979, 7\u201310 (in Russian)"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","year":"1979","author":"M.R. Garey","key":"16_CR11","unstructured":"M.R. GAREY, D.S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979."},{"key":"16_CR12","first-page":"150","volume-title":"Proc. Found. of Comp. Theory, LNCS 278","author":"D. Geidmanis","year":"1988","unstructured":"D. GEIDMANIS, On the capabilities of alternating and nondeterministic multitape automata. Proc. Found. of Comp. Theory, LNCS 278, Springer, Berlin, 1988, 150\u2013154."},{"issue":"1","key":"16_CR13","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/0022-0000(85)90063-7","volume":"31","author":"J. Hromkovi\u010d","year":"1985","unstructured":"J. HROMKOVI\u010c, On the power of alternation in automata theory. Journ. of Comp.and System Sci., Vol. 31, No. 1, 1985, 28\u201339","journal-title":"Journ. of Comp.and System Sci."},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/S0019-9958(68)90901-7","volume":"13","author":"M.A. Harrison","year":"1968","unstructured":"M.A. HARRISON and O.H. IBARRA, Multi-tape and multi-head pushdown automata. Information and Control, 13, 1968, 433\u2013470.","journal-title":"Information and Control"},{"key":"16_CR15","first-page":"287","volume-title":"LNCS 529","author":"J. Ka\u0146eps","year":"1991","unstructured":"J. KA\u0145EPS, Regularity of one-letter languages acceptable by 2-way finite probabilistic automata. LNCS 529, Springer, Berlin, 1991, 287\u2013296."},{"key":"16_CR16","first-page":"63","volume":"1","author":"J. Ka\u0146eps","year":"1989","unstructured":"J. KA\u0145EPS, Stochasticity of languages recognized by two-way finite probabilistic automata. Diskretnaya matematika, 1 (1989), 63\u201377 (Russian).","journal-title":"Diskretnaya matematika"},{"key":"16_CR17","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/3-540-54458-5_73","volume":"529","author":"J. Ka\u0146eps","year":"1991","unstructured":"J. KA\u0145EPS, Regularity of one-letter languages acceptable by 2-way finite probabilistic automata. Lecture Notes in Computer Science, 529 (1991), 287\u2013296.","journal-title":"Lecture Notes in Computer Science"},{"key":"16_CR18","first-page":"355","volume":"452","author":"J. Ka\u0146eps","year":"1990","unstructured":"J. KA\u0145EPS, R. FREIVALDS, Minimal nontrivial apace complexity of probabilistic one-way Turing machines. LNCS, Springer, 452 1990, 355\u2013361.","journal-title":"LNCS, Springer"},{"key":"16_CR19","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/0890-5401(87)90057-5","volume":"75","author":"M. Karpinski","year":"1987","unstructured":"M. KARPINSKI, R. VERBEEK, On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes. Information and Computation, 75 (1987), 178\u2013189.","journal-title":"Information and Computation"},{"key":"16_CR20","unstructured":"J.G.KEMENY, J.L.SNELL, Finite Markov Chains. Van Nostrand, 1960."},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"J.G.KEMENY, J.L.SNELL, A.W.KNAPP, Denumerable Markov Chains. Springer-Verlag, 1976.","DOI":"10.1007\/978-1-4684-9455-6"},{"key":"16_CR22","first-page":"506","volume-title":"LNCS 115","author":"K.N. King","year":"1981","unstructured":"K.N. KING, Alternating multihead finite automata. LNCS 115, Springer, Berlin, 1981, 506\u2013520."},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"R.E.LADNER, R.J.LIPTON, and L.J.STOCKMEYER, Alternating push-down automata. Conf. Rec. IEEE 19th Ann. Symp. on Found. of Comp. Sci. (1978), 92\u2013106.","DOI":"10.1109\/SFCS.1978.6"},{"key":"16_CR24","unstructured":"H.R.LEWIS, and CH.H.PAPADIMITRIOU, Elements of the Theory of Computation. Prentice-Hall, 1981, 466 pages."},{"key":"16_CR25","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/S0019-9958(68)90353-7","volume":"12","author":"M. Nasu","year":"1968","unstructured":"M. NASU and N. HONDA, Fuzzy events realized by finite probabilistic automata. Information and Control, 12, 1968, 284\u2013303.","journal-title":"Information and Control"},{"key":"16_CR26","unstructured":"CH.H.PAPADIMITRIOU, Computational Complexity. Addison-Wesley, 1994."},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"A. PAZ, Some aspects of probabilistic automata, Information and Control, 9(1966)","DOI":"10.1016\/S0019-9958(66)90092-1"},{"key":"16_CR28","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M. O. Rabin","year":"1963","unstructured":"M. O. RABIN, Probabilistic automata, Information and Control, 6(1963), 230\u2013245.","journal-title":"Information and Control"},{"key":"16_CR29","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J.C. Shepherdson","year":"1959","unstructured":"J.C. SHEPHERDSON, The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(1959), 198\u2013200.","journal-title":"IBM Journal of Research and Development"},{"key":"16_CR30","unstructured":"B. A. TRAKHTENBROT, Y. M. BARZDIN, Finite Automata: Behaviour and Synthesis. North-Holland, 1973."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:17:50Z","timestamp":1605629870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}