{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:00:32Z","timestamp":1725548432028},"publisher-location":"Berlin\/Heidelberg","reference-count":26,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540541314"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0019368","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T05:26:33Z","timestamp":1132637193000},"page":"565-613","source":"Crossref","is-referenced-by-count":16,"title":["Complexity of probabilistic versus deterministic automata"],"prefix":"10.1007","author":[{"given":"R\u016bsi\u0146\u0160","family":"Freivalds","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","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, 15: 245\u2013248, 1965 (Russian).","journal-title":"Problemy kibernetiki"},{"key":"16_CR2","unstructured":"A.A.Bukhshtab. Number theory. Uchpedgiz, 1960(Russian)"},{"key":"16_CR3","first-page":"191","volume":"1","author":"P.L. \u010cebi\u0161ev","year":"1944","unstructured":"P.L. \u010cebi\u0161ev. On prime numbers. In: Opera omnia, 1: 191\u2013207, Gosgiz (Moscow), 1944.","journal-title":"Opera omnia"},{"key":"16_CR4","first-page":"201","volume":"2","author":"R. Freivalds","year":"1975","unstructured":"R. Freivalds. Fast computation by probabilistic Turing machines. Theorija algoritmov i programm. 2: 201\u2013205, 1975 (Russian).","journal-title":"Theorija algoritmov i programm"},{"key":"16_CR5","unstructured":"R.Freivalds. Probabilistic machines can use less running time. Information Processing'77 (Proc. IFIP Congress'77), 839\u2013842, 1977."},{"key":"16_CR6","unstructured":"R.Freivalds. Speeding of recognition of languages by usage of random number generators. Problemy kibernetiki, 36: 209\u2013224 (Russian)."},{"key":"16_CR7","first-page":"99","volume":"15","author":"R. Freivalds","year":"1979","unstructured":"[Fre 791] R. Freivalds. Recognition of languages by finite probabilistic multitape and multihead automata. \u2014 Problemy peredachi informacii, 15: 99\u2013106, 1979 (Russian).","journal-title":"Problemy peredachi informacii"},{"key":"16_CR8","unstructured":"R.Freivalds. On increase of the number of the number of states in determinization of finite probabilistic automata. \u2014 Avtomatika i vychislitelnaja technika, No.3, 39\u201342, 1982 (Russian)."},{"key":"16_CR9","unstructured":"R.Freivalds. Methods and languages to prove the power of probabilistic machines. Information Processing'83 (Proc. IFIP Congress'83), 157\u2013162, 1983."},{"key":"16_CR10","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/3-540-12689-9_101","volume":"158","author":"R. Freivalds","year":"1983","unstructured":"[Fre 831] R. Freivalds. Space and reversal complexity of probabilistic one-way Turing machines. Lecture Notes in Computer Science, 158: 159\u2013169, 1983.","journal-title":"Lecture Notes in Computer Science"},{"key":"16_CR11","unstructured":"N.Z.Gabbasov and T.A.Murtazina. Improvement for the bound in the reduction theorem by Rabin. Algorithms and automata, Kazan University Press, 7\u201310, 1978 (Russian)."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"J.T.Gill III. Computational complexity of probabilistic Turing machines. Proc. 6th ACM Symposium on Theory of Computation, 91\u201395, 1974.","DOI":"10.1145\/800119.803889"},{"key":"16_CR13","unstructured":"F.Hennie. Introduction to Computability. Addison Wesley, 1977."},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BFb0029629","volume":"452","author":"J. Kaneps","year":"1990","unstructured":"J. Kaneps and R. Freivalds. Minimal nontrivial space complexity of probabilistic one-way Turing machines. Lecture Notes in Computer Science. 452: 355\u2013361, 1990.","journal-title":"Lecture Notes in Computer Science"},{"key":"16_CR15","volume-title":"Introduction into Theory of Automata","author":"V.B. Kudrjavcev","year":"1985","unstructured":"V.B. Kudrjavcev, S.V. Aleshin, A.S. Podkolzin. Introduction into Theory of Automata. Nauka, Moscow, 1985 (Russian)."},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"R.E.Ladner, R.J.Lipton and L.J.Stockmeyer. Alternating pushdown automata. Proc. IEEE Symp. on Foundations of Computer Science, 92\u2013106, 1978.","DOI":"10.1109\/SFCS.1978.6"},{"key":"16_CR17","unstructured":"A.Lorencs. The problems of structural analysis of probabilistic automata and transformers of probabilistic distributions. \u2014 In: Probabilistic automata and applications. Kazan University Press, 16\u201322, 1986 (Russian)."},{"key":"16_CR18","first-page":"88","volume":"10","author":"O.B. Lupanov","year":"1963","unstructured":"O.B. Lupanov. On synthesis of some classes of control systems. Problemy kibernetiki, 10: 88\u201396, 1963 (Russian).","journal-title":"Problemy kibernetiki"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/S0019-9958(66)90092-1","volume":"9","author":"A. Paz","year":"1966","unstructured":"A. Paz. Some aspects of probabilistic automata. Information and Control, 9: 26\u201360, 1966.","journal-title":"Information and Control"},{"key":"16_CR20","unstructured":"M.O.Rabin. Two-way finite automata. Summaries of Talks Presented at the Summer Institute of Symbolic Logic (Cornell Univ., 1957), 2nd ed. Comm. Res. Div., Inst. Defense Anal., Princeton, N.J., 366\u2013369, 1960."},{"key":"16_CR21","first-page":"230","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"M.O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 6: 230\u2013245, 1963.","journal-title":"IBM Journal of Research and Development"},{"key":"16_CR22","doi-asserted-by":"publisher","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: 230\u2013244, 1963.","journal-title":"Information and Control"},{"key":"16_CR23","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:198\u2013200, 1959.","journal-title":"IBM Journal of Research and Development"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"R.E.Stearns, J.Hartmanis and P.M.Lewis II. Hierarchies of memory limited computation. In: Proc. IEEE Symp. on Switching Circuit Theory and Logical Design, 179\u2013190, 1965.","DOI":"10.1109\/FOCS.1965.11"},{"key":"16_CR25","unstructured":"B.A.Trakhtenbrot and J.M.Barzdin. Finite Automata (Behaviour and Synthesis). North-Holland, 1972."},{"key":"16_CR26","volume-title":"Research in Mathematical Logic and Theory of Algorithms","author":"B.A. Trakhtenbrot","year":"1974","unstructured":"B.A. Trakhtenbrot. Notes on complexity of computation by probabilistic machines. In: Research in Mathematical Logic and Theory of Algorithms, Comp. Ctr. Acad. Sci. USSR, Moscow, 1974 (Russian)."}],"container-title":["Lecture Notes in Computer Science","Baltic Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0019368.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:42:19Z","timestamp":1607550139000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0019368"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540541314"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0019368","relation":{},"subject":[]}}