{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:15Z","timestamp":1760202615377},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135224"},{"type":"electronic","value":"9783642135231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13523-1_5","type":"book-chapter","created":{"date-parts":[[2010,6,23]],"date-time":"2010-06-23T04:34:26Z","timestamp":1277267666000},"page":"11-20","source":"Crossref","is-referenced-by-count":1,"title":["Finite State Transducers with Intuition"],"prefix":"10.1007","author":[{"given":"Ruben","family":"Agadzanyan","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":"5_CR1","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Why Sometimes Probabilistic Algorithms Can Be More Effective","author":"F.M. Ablayev","year":"1986","unstructured":"Ablayev, F.M., Freivalds, R.: Why Sometimes Probabilistic Algorithms Can Be More Effective. LNCS, vol.\u00a0233, pp. 1\u201314. Springer, Heidelberg (1986)"},{"key":"5_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. John Wiley & Sons, Chichester (2000)"},{"key":"5_CR3","volume-title":"Algorithmic Number Theory","author":"E. Bach","year":"1996","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory, vol.\u00a01. MIT Press, Cambridge (1996)"},{"key":"5_CR4","unstructured":"B\u0101rzdi\u0146\u0161, J. (Barzdin, J.M.): On a Class of Turing Machines (Minsky Machines). Algebra i Logika\u00a03(1) (1963) (Russian); Review in The Journal of Symbolic Logic\u00a032(4), 523\u2013524 (1967)"},{"key":"5_CR5","series-title":"Lecture Notes in Computer Science","first-page":"565","volume-title":"Mathematical Foundations of Computer Science 1995","author":"C. Damm","year":"1995","unstructured":"Damm, C., Holzer, M.: Automata that take advice. In: H\u00e1jek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol.\u00a0969, pp. 565\u2013613. Springer, Heidelberg (1995)"},{"issue":"4","key":"5_CR6","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1145\/146585.146599","volume":"39","author":"C. Dwork","year":"1992","unstructured":"Dwork, C., Stockmeyer, L.: Finite state verifiers I: the power of interaction. Journal of the Association for Computing Machinery\u00a039(4), 800\u2013828 (1992)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"4","key":"5_CR7","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P. Erd\u00f6s","year":"1947","unstructured":"Erd\u00f6s, P.: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society\u00a053(4), 292\u2013294 (1947)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"5_CR8","unstructured":"Fagin, R.: Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In: Karp, R. (ed.) SIAM-AMS Proceedings of Complexity of Computation, vol.\u00a07, pp. 27\u201341 (1974)"},{"issue":"1","key":"5_CR9","first-page":"60","volume":"239","author":"R. Freivalds","year":"1978","unstructured":"Freivalds, R. (Freivald, R.V.): Recognition of languages with high probability on different classes of automata. Dolady Akademii Nauk SSSR\u00a0239(1), 60\u201362 (1978) (Russian)","journal-title":"Dolady Akademii Nauk SSSR"},{"issue":"4","key":"5_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(81)90057-0","volume":"13","author":"R. Freivalds","year":"1981","unstructured":"Freivalds, R.: Projections of Languages Recognizable by Probabilistic and Alternating Finite Multitape Automata. Information Processing Letters\u00a013(4\/5), 195\u2013198 (1981)","journal-title":"Information Processing Letters"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/BFb0019368","volume-title":"Baltic Computer Science","author":"R. Freivalds","year":"1991","unstructured":"Freivalds, R.: Complexity of Probabilistic Versus Deterministic Automata. In: Barzdins, J., Bjorner, D. (eds.) Baltic Computer Science. LNCS, vol.\u00a0502, pp. 565\u2013613. Springer, Heidelberg (1991)"},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1142\/S0129054108005826","volume":"19","author":"R. Freivalds","year":"2008","unstructured":"Freivalds, R.: Non-Constructive Methods for Finite Probabilistic Automata. International Journal of Foundations of Computer Science\u00a019(3), 565\u2013580 (2008)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"5_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-642-02979-0_26","volume-title":"Implementation and Application of Automata","author":"R. Freivalds","year":"2009","unstructured":"Freivalds, R.: Amount of nonconstructivity in finite automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol.\u00a05642, pp. 227\u2013236. Springer, Heidelberg (2009)"},{"key":"5_CR14","unstructured":"Freivalds, R.: Multiple usage of random bits by finite automata. Unpublished manuscript (2010)"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/BF01208503","volume":"36","author":"D. Hilbert","year":"1890","unstructured":"Hilbert, D.: Uber die Theorie der algebraischen Formen. Mathematische Annalen\u00a036, 473\u2013534 (1890)","journal-title":"Mathematische Annalen"},{"key":"5_CR16","first-page":"191","volume":"28","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M., Lipton, R.: Turing machines that take advice. L\u2019 Enseignement Mathematique\u00a028, 191\u2013209 (1982)","journal-title":"L\u2019 Enseignement Mathematique"},{"key":"5_CR17","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Problems in Information Transmission\u00a01, 1\u20137 (1965)","journal-title":"Problems in Information Transmission"},{"key":"5_CR18","first-page":"1413","volume":"14","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A.: On the notion of a random sequence. Soviet Mathematics Doklady\u00a014, 1413\u20131416 (1973)","journal-title":"Soviet Mathematics Doklady"},{"issue":"6","key":"5_CR19","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Information and Control\u00a09(6), 602\u2013619 (1966)","journal-title":"Information and Control"},{"key":"5_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Heidelberg (1997)","edition":"2"},{"issue":"4","key":"5_CR21","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.ipl.2004.02.005","volume":"90","author":"H. Nishimura","year":"2004","unstructured":"Nishimura, H., Yamakami, T.: Polynomial time quantum computation with advice. Information Processing Letters\u00a090(4), 195\u2013204 (2004)","journal-title":"Information Processing Letters"},{"issue":"3","key":"5_CR22","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C.-P. Schnorr","year":"1971","unstructured":"Schnorr, C.-P.: A unified approach to the definition of random sequences. Mathematical Systems Theory\u00a05(3), 246\u2013258 (1971)","journal-title":"Mathematical Systems Theory"},{"issue":"4","key":"5_CR23","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C.-P. Schnorr","year":"1973","unstructured":"Schnorr, C.-P.: Process Complexity and Effective Random Tests. Journal of Computer and System Sciences\u00a07(4), 376\u2013388 (1973)","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR24","unstructured":"Spencer, J.: Nonconstructive methods in discrete mathematics. In: Rota, G.-C. (ed.) Studies in Mathematics, MAA, vol.\u00a017, pp. 142\u2013178 (1978)"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Stearns, R.E., Hartmanis, J., Lewis II, P.M.: Hierarchies of memory limited computations. In: Proceedings of FOCS, pp. 179\u2013190 (1965)","DOI":"10.1109\/FOCS.1965.11"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/978-3-540-24618-3_29","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"K. Tadaki","year":"2004","unstructured":"Tadaki, K., Yamakami, T., Lin, J.C.H.: Theory of One Tape Linear Time Turing Machines. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol.\u00a02932, pp. 335\u2013348. Springer, Heidelberg (2004)"},{"key":"5_CR27","unstructured":"Yamakami, T.: Swapping lemmas for regular and context-free languages with advice. The Computing Research Repository (CoRR), CoRR abs\/0808.4122 (2008)"}],"container-title":["Lecture Notes in Computer Science","Unconventional Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13523-1_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:06:19Z","timestamp":1619784379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13523-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135224","9783642135231"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13523-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}