{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:12Z","timestamp":1759639092216,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434535"},{"type":"electronic","value":"9783540460114"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46011-x_1","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T22:54:16Z","timestamp":1182207256000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Automata: From Uncertainty to Quantum"],"prefix":"10.1007","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[]},{"given":"Elena","family":"Calude","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,19]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R. 1-way quantum finite automata: strengths, weaknesses and generalizations, Proceedings of 39th IEEE FOCS (1998), 332\u2013341.","DOI":"10.1109\/SFCS.1998.743469"},{"key":"1_CR2","unstructured":"Ambainis, A., Watrous, J. Two-way finite automata with quantum and classical states, Technical Report, CC\/9911009, 1999."},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1145\/321574.321577","volume":"17","author":"Z. Bavel","year":"1970","unstructured":"Bavel, Z., and Muller, D. E. Connectivity and reversibility in automata, J. Assoc. Comput. Mach. 17 (1970), 231\u2013240.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195","volume":"1","author":"J. S. Bell","year":"1964","unstructured":"Bell, J. S. On the Einstein Podolsky Rosen paradox, Physics, 1 (1964), 195\u2013200. Reprinted in [5] pp. 14\u201321.","journal-title":"Physics"},{"key":"1_CR5","unstructured":"Bell, J. S. Speakable and Unspeakable in Quantum Mechanics, Cambridge University Press, Cambridge, 1987."},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Brauer, W. Automatentheorie, Teubner, Stuttgart, 1984.","DOI":"10.1007\/978-3-322-92151-2"},{"key":"1_CR7","first-page":"101","volume":"2","author":"P. W. Bridgman","year":"1934","unstructured":"Bridgman, P. W. A physicists second reaction to Mengenlehre, Scripta Mathematica 2 (1934), 101\u2013117, 224\u2013234.","journal-title":"Scripta Mathematica"},{"key":"1_CR8","unstructured":"Brodsky, A., Pippenger, N. Characterisation of 1-way quantum finite automata, quantph\/9903014, 1999."},{"issue":"3","key":"1_CR9","first-page":"1","volume":"38","author":"A. S. Calude","year":"2001","unstructured":"Calude, A. S. The journey of the four colour theorem through time, The New Zealand Mathematics Magazine 38, 3 (2001), 1\u201310.","journal-title":"The New Zealand Mathematics Magazine"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Calude, C. S., Calude, E. Bisimulations and behaviour of nondeterministic automata, in G. Rozenberg, W. Thomas (eds.) Developments in Language Theory. Foundations, Applications, and Perspectives, World Scientific, Singapore, 2000, 60\u201370.","DOI":"10.1142\/9789812792464_0006"},{"key":"1_CR11","first-page":"47","volume":"6","author":"C. S. Calude","year":"2001","unstructured":"Calude, C. S., Calude, E., Chiu, T., Dumitrescu, M., and Nicolescu, R. Testing computational complementarity for Mermin automata, J. Multi Valued Logic, 6 (2001), 47\u201365.","journal-title":"J. Multi Valued Logic"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0168-0072(97)00039-0","volume":"90","author":"C. S. Calude","year":"1997","unstructured":"Calude, C. S., Calude, E., Khoussainov, B. Deterministic automata: Simulation, universality and minimality, Annals of Applied and Pure Logic 90, 1\u20133 (1997), 263\u2013276.","journal-title":"Annals of Applied and Pure Logic"},{"issue":"1","key":"1_CR13","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0304-3975(98)00221-7","volume":"242","author":"C. S. Calude","year":"2000","unstructured":"Calude, C. S., Calude, E., Khoussainov, B. Finite nondeterministic automata: Simulation and minimality, Theoret. Comput. Sci. 242, 1\u20132 (2000), 219\u2013235.","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Calude, C. S., Calude, E., Svozil, K. Computational complementarity for probabilistic automata, in C. Martin-Vide, V. Mitrana (eds.). Where Mathematics, Computer Science, Linguistics and Biology Meet, Kluwer, Amsterdam 2000, 99\u2013113.","DOI":"10.1007\/978-94-015-9634-3_9"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1007\/BF02435752","volume":"36","author":"C. S. Calude","year":"1997","unstructured":"Calude, C. S., Calude, E., Svozil, K., and Yu, S. Physical versus computational complementarity I, International Journal of Theoretical Physics 36 (1997), 1495\u20131523.","journal-title":"International Journal of Theoretical Physics"},{"key":"1_CR16","first-page":"139","volume":"66","author":"C. S. Calude","year":"1998","unstructured":"Calude, C. S., Calude, E., \u015etef\u0103anescu, C. Computational complementarity for Mealy automata, EATCS Bull. 66 (1998), 139\u2013149.","journal-title":"EATCS Bull."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Chaitin, G. J. ewblock An improvement on a theorem by E. F. Moore. IEEE Transactions on Electronic Computers EC-14 (1965), 466\u2013467.","DOI":"10.1109\/PGEC.1965.264155"},{"key":"1_CR18","unstructured":"Ciamarra, M. P. Quantum reversibility and a new model of quantum automaton, in R. Freivalds (ed.). The 13th International Symposium on Foundations of Computation Theory (FCT\u20192001), Riga, Latvia, Springer-Verlag, Lect. Notes Comput. Sci. 2138, 2001, 376\u2013379."},{"key":"1_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8841-8","volume-title":"An Introduction to Hilbert Space and Quantum Logic","author":"D. W. Cohen","year":"1989","unstructured":"Cohen, D. W. An Introduction to Hilbert Space and Quantum Logic, Springer, New York, 1989."},{"key":"1_CR20","volume-title":"Regular Algebra and Finite Machines","author":"J. H. Conway","year":"1971","unstructured":"Conway, J. H. Regular Algebra and Finite Machines, Chapman and Hall Ltd., London, 1971."},{"key":"1_CR21","unstructured":"Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer, Proceedings of the Royal Society London, A 400(1985), 97\u2013119."},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1103\/PhysRev.47.777","volume":"47","author":"A. Einstein","year":"1935","unstructured":"Einstein, A., Podolsky, B., and Rosen, N. Can quantum-mechanical description of physical reality be considered complete? Physical Review 47 (1935), 777\u2013780.","journal-title":"Physical Review"},{"issue":"8","key":"1_CR23","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1007\/BF02085960","volume":"22","author":"D. Finkelstein","year":"1983","unstructured":"Finkelstein, D., and Finkelstein, S. R. Computational complementarity, International Journal of Theoretical Physics 22, 8 (1983), 753\u2013779.","journal-title":"International Journal of Theoretical Physics"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1063\/1.1665890","volume":"13","author":"D. J. Foulis","year":"1972","unstructured":"Foulis, D. J., and Randall, C. Operational statistics. i. Basic concepts, Journal of Mathematical Physics 13 (1972), 1667\u20131675.","journal-title":"Journal of Mathematical Physics"},{"key":"1_CR25","unstructured":"Frank, M., Knight, T., Margolus, N. Reversibility in optimally scalable computer architectures, In Unconventional Models of Computation, C. S. Calude, J. Casti, M. Dinneen, Eds., Springer-Verlag, 1998, 165\u2013182."},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/S0019-9958(61)80003-X","volume":"4","author":"A. Gill","year":"1961","unstructured":"Gill, A. State-identification experiments in finite automata, Information and Control 4 (1961), 132\u2013154.","journal-title":"Information and Control"},{"key":"1_CR27","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1145\/320932.320938","volume":"5","author":"S. Ginsburg","year":"1958","unstructured":"Ginsburg, S. On the length of the smallest uniform experiment which distinguishes the terminal states of the machine, J. Assoc. Comput. Mach. 5 (1958), 266\u2013280.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR28","unstructured":"Giuntini, R. Quantum Logic and Hidden Variables. BI Wissenschaftsverlag, Mannheim, 1991."},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Greenberger, D. B., Horne, M., and Zeilinger, A. Multiparticle interferometry and the superposition principle, Physics Today 46 (August 1993), 22\u201329.","DOI":"10.1063\/1.881360"},{"key":"1_CR30","volume-title":"Quantum Computing","author":"J. Gruska","year":"1999","unstructured":"Gruska, J. Quantum Computing, McGraw-Hill, London, 1999."},{"key":"1_CR31","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"Hopcroft, J. E., and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA, 1979."},{"issue":"1","key":"1_CR32","first-page":"59","volume":"17","author":"S. Kochen","year":"1967","unstructured":"Kochen, S., and Specker, E. P. The problem of hidden variables in quantum mechanics, Journal of Mathematics and Mechanics 17, 1 (1967), 59\u201387.","journal-title":"Journal of Mathematics and Mechanics"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J. On the power of quantum finite state automata, Proceedings of 38th IEEE FOCS, 1997, 66\u201375.","DOI":"10.1109\/SFCS.1997.646094"},{"key":"1_CR34","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1844-9","volume-title":"Automata and Computability","author":"D. Kozen","year":"1997","unstructured":"Kozen, D. Automata and Computability, Springer-Verlag, NewYork, 1997."},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(97)00028-5","volume":"201","author":"C. Moore","year":"1998","unstructured":"Moore, C. Dynamical recognizers: real-time language recognition by analogue computers, Theoret. Comput. Sci. 201 (1998), 99\u2013136.","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Moore, C. Email to C. S. Calude, 10 May 2001.","DOI":"10.1088\/2058-7058\/14\/3\/13"},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0304-3975(98)00191-1","volume":"237","author":"C. Moore","year":"2000","unstructured":"Moore, C. Crutchfield, J. P. Quantum automata and quantum grammars, Theoret. Comput. Sci. 237 (2000), 275\u2013306.","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR38","first-page":"129","volume-title":"Automata Studies","author":"E. F. Moore","year":"1956","unstructured":"Moore, E. F. Gedanken-experiments on sequential machines, In Automata Studies, C. E. Shannon and J. McCarthy, Eds., Princeton University Press, Princeton, 1956, 129\u2013153."},{"key":"1_CR39","unstructured":"Paschen, K. Quantum finite automata using ancilla qubits, manuscript, May 2001."},{"key":"1_CR40","volume-title":"Shadows of the Minds, A Search for the Missing Science of Consciousness","author":"R. Penrose","year":"1994","unstructured":"Penrose, R. Shadows of the Minds, A Search for the Missing Science of Consciousness, Oxford University Press, Oxford, 1994."},{"key":"1_CR41","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 6 (1963), 230\u2013244.","journal-title":"Information and Control"},{"key":"1_CR42","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107325630","volume-title":"Computation and Automata","author":"A. Salomaa","year":"1985","unstructured":"Salomaa, A. Computation and Automata, Cambridge University Press, Cambridge, 1985."},{"key":"1_CR43","doi-asserted-by":"crossref","unstructured":"Svozil, K. Randomness & Undecidability in Physics, World Scientific, Singapore, 1993.","DOI":"10.1142\/1524"},{"key":"1_CR44","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1007\/BF01889696","volume":"20","author":"R. Wright","year":"1990","unstructured":"Wright, R. Generalized urn models, Foundations of Physics 20 (1990), 881\u2013903.","journal-title":"Foundations of Physics"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46011-X_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T09:02:12Z","timestamp":1737104532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46011-X_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434535","9783540460114"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/3-540-46011-x_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"19 March 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}