{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:10:44Z","timestamp":1725455444448},"publisher-location":"Berlin\/Heidelberg","reference-count":28,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016230","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"1-14","source":"Crossref","is-referenced-by-count":11,"title":["Why sometimes probabilistic algorithms can be more effective"],"prefix":"10.1007","author":[{"given":"Farid M.","family":"Ablaev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"F.M.Ablaev, On the problem of reduction of automata, Izvestija VUZ. Matematika, 1980, No.3, 75\u201377 (Russian)."},{"key":"1_CR2","unstructured":"F.M.Ablaev, Capabilities of probabilistic machines to represent languages in real time, Izvestija VUZ. Matematika, 1985, No.7, 32\u201340 (Russian)."},{"key":"1_CR3","first-page":"245","volume":"15","author":"J.M. Barzdin","year":"1965","unstructured":"J.M. Barzdin, Complexity of recognition of palindromes by Turing machines, Problemy kibernetiki, v.15, Moscow, Nauka, 1965, 245\u2013248 (Russian).","journal-title":"Problemy kibernetiki"},{"issue":"4","key":"1_CR4","first-page":"699","volume":"189","author":"J.M. Barzdin","year":"1969","unstructured":"J.M. Barzdin, On computability by probabilistic machines, Doklady AN SSSR, 1969, v.189, No.4, 699\u2013702 (Russian).","journal-title":"Doklady AN SSSR"},{"key":"1_CR5","volume-title":"Foundations of the theory of probabilistic automata","author":"R.G. Bukharaev","year":"1985","unstructured":"R.G. Bukharaev, Foundations of the theory of probabilistic automata, Moscow, Nauka, 1985."},{"key":"1_CR6","volume-title":"An introduction to probability theory and its applications, v.1","author":"W. Feller","year":"1957","unstructured":"W. Feller, An introduction to probability theory and its applications, v.1, New York et al., John Wiley, 1957."},{"key":"1_CR7","first-page":"201","volume":"233","author":"R. Freivalds","year":"1975","unstructured":"R. Freivalds, Fast computation by probabilistic Turing machines, Ucenye Zapiski Latvijskogo Gosudarstvennogo Universiteta, 1975, v.233, 201\u2013205 (Russian)","journal-title":"Ucenye Zapiski Latvijskogo Gosudarstvennogo Universiteta"},{"key":"1_CR8","unstructured":"R.Freivalds, Probabilistic machines can use less running time, in: Information Processing '77, IFIP (North Holland, 1977), 839\u2013842."},{"issue":"1","key":"1_CR9","first-page":"60","volume":"239","author":"R. Freivalds","year":"1978","unstructured":"R. Freivalds, Language recognition with high probability by various classes of automata, Doklady AN SSSR, 1978, v.239, No.1, 60\u201362 (Russian).","journal-title":"Doklady AN SSSR"},{"key":"1_CR10","first-page":"209","volume-title":"Speeding of recognition of languages by usage of random number generators, Problemy kibernetiki, v.36","author":"R. Freivalds","year":"1979","unstructured":"R. Freivalds, Speeding of recognition of languages by usage of random number generators, Problemy kibernetiki, v.36, Moscow, Nauka, 1979, 209\u2013224 (Russian)."},{"key":"1_CR11","unstructured":"R.Freivalds, Finite identification of general recursive functions by probabilistic strategies, Proc. Conference FCT, 1979, 138\u2013145."},{"key":"1_CR12","unstructured":"R.Freivalds, On principal capabilities of probabilistic algorithms in inductive inference, Semiotika i informatika, 1979, No.12, 137\u2013140 (Russian)."},{"key":"1_CR13","unstructured":"R.Freivalds, A probabilistic reducibility of sets, Proc. USSR Conference on Mathematical Logics, 1979, 137 (Russian)."},{"key":"1_CR14","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, Springer, 1981, v.118, 33\u201345.","journal-title":"Lecture Notes in Computer Science, Springer"},{"key":"1_CR15","unstructured":"R.Freivalds, Capabilities of various models of probabilistic one-way automata, Izvestija VUZ. Matematika, 1981, No.5, 26\u201334 (Russian)."},{"key":"1_CR16","first-page":"241","volume":"27","author":"R. Freivalds","year":"1983","unstructured":"R. Freivalds, Characterization of capabilities of the simplest method for proving the advantages of probabilistic automata over deterministic ones, Latvijskij matematiceskij ezegodnik, 1983, v.27, 241\u2013251 (Russian).","journal-title":"Latvijskij matematiceskij ezegodnik"},{"key":"1_CR17","first-page":"155","volume":"29","author":"R. Freivalds","year":"1985","unstructured":"R. Freivalds, Advantages of probabilistic 3-head finite automata over deterministic multi-head ones, Latvijskij matematiceskij ezegodnik, 1985, v.29, 155\u2013163 (Russian).","journal-title":"Latvijskij matematiceskij ezegodnik"},{"key":"1_CR18","volume-title":"Formal grammars and languages","author":"A.V. Gladkij","year":"1973","unstructured":"A.V. Gladkij, Formal grammars and languages, Moscow, Nauka, 1973."},{"key":"1_CR19","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E.M. Gold","year":"1967","unstructured":"E.M. Gold, Language identification in the limit, Information and Control, 1967, v.10, 447\u2013474.","journal-title":"Information and Control"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"K. de Leeuw, E.F.Moore, C.E.Shannon and N.Shapiro, Computability by probabilistic machines, Automata Studies, Princeton University Press, 1956, 183\u2013212.","DOI":"10.1515\/9781400882618-010"},{"key":"1_CR21","unstructured":"N.R.Nigmatullin, Towards the problem of reduction of \u03c9-automata, Verojatnostnye metodi i kibernetika, Kazan University Press, 1979, 61\u201367 (Russian)."},{"key":"1_CR22","unstructured":"L.Pitt, Probabilistic inductive inference, Yale University, YALEU \/DCS\/ TR-400, June 1985."},{"issue":"3","key":"1_CR23","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, 1963, v.6, No.3, 230\u2013245.","journal-title":"Information and Control"},{"key":"1_CR24","volume-title":"Theory of recursive functions and effective computability","author":"H. Rogers Jr.","year":"1967","unstructured":"H. Rogers Jr., Theory of recursive functions and effective computability, New York, McGraw Hill, 1967."},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"R.E.Stearns, J.Hartmanis and P.M.Lewis II, Hierarchies of memory limited computation, Proc. IEEE Symposium on Switching Circuit Theory and Logical Design, 1965, 179\u2013190.","DOI":"10.1109\/FOCS.1965.11"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"P.Turakainen, On probabilistic automata and their generalizations, Suomalais, tiedenkat. toimituks., 1968, v.53.","DOI":"10.5186\/aasfm.1969.429"},{"key":"1_CR27","unstructured":"A.V.Vaiser, Notes on complexity measures in probabilistic computations, in: Control systems, v.1, Tomsk University Press, 1975, 182\u2013196 (Russian)."},{"key":"1_CR28","unstructured":"S.V.Yablonskiy, On lagorithmic difficulties in minimal circuit synthesis, Problemy kibernetiki, v.2, Moscow, Fizmatgiz, 75\u2013121 (Russian)."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016230.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:35:28Z","timestamp":1607549728000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/bfb0016230","relation":{},"subject":[]}}