{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T02:04:41Z","timestamp":1768529081936,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":153,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642082306","type":"print"},{"value":"9783662076750","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"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":[[1997]]},"DOI":"10.1007\/978-3-662-07675-0_1","type":"book-chapter","created":{"date-parts":[[2013,3,26]],"date-time":"2013-03-26T18:44:33Z","timestamp":1364323473000},"page":"1-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity: A Language-Theoretic Point of View"],"prefix":"10.1007","author":[{"given":"Cristian","family":"Calude","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,26]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"H. Abelson, Lower bounds on information transfer in distributed computations. In: Proc. 29th Annual IEEE FOCS, IEEE 1978, 151\u2013158.","DOI":"10.1109\/SFCS.1978.22"},{"key":"1_CR2","volume-title":"Word problems II: The Oxford Book","year":"1980","unstructured":"S. I. Adian, W. W. Boone, G. Higman (eds.), Word problems II: The Oxford Book, North-Holland, New York, 1980."},{"key":"1_CR3","volume-title":"Recognizing primes in random polynomial time, Technical Report, Department of Computer Science","author":"LM Adleman","year":"1988","unstructured":"L. M. Adleman, M. A. Huang, Recognizing primes in random polynomial time, Technical Report, Department of Computer Science, Washington, State University, 1988."},{"issue":"5-6","key":"1_CR4","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0375-9601(83)90863-0","volume":"98","author":"David Z. Albert","year":"1983","unstructured":"D. Z. Albert, On quantum-mechanical automata, Phys. Lett. 98A (1983), 249\u2013252.","journal-title":"Physics Letters A"},{"key":"1_CR5","volume-title":"Minimalism: Art of Circumstance","author":"K Baker","year":"1988","unstructured":"K. Baker, Minimalism: Art of Circumstance, Abbeville Press, New York, 1988."},{"key":"1_CR6","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T Baker","year":"1975","unstructured":"T. Baker, J. Gill, R. Solovay, Relativizations of the problem P =?NP question, SIAM J. Comput. 4 (1975), 431\u2013442.","journal-title":"SIAM J. Comput."},{"key":"1_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"JL Balcazar","year":"1988","unstructured":"J. L. Balcazar, J. Diaz, J. Gabarro, Structural Complexity I, Springer-Verlag, New York, 1988."},{"key":"1_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-75357-2","volume-title":"Structural Complexity II","author":"JL Balcazar","year":"1990","unstructured":"J. L. Balcazar, J. Diaz, J. Gabarro, Structural Complexity II, Springer-Verlag, New York, 1990."},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01342185","volume":"29","author":"P Benioff","year":"1982","unstructured":"P. Benioff, Quantum mechanical models of Turing machines, J. Stat. Phys. 29 (1982), 515\u2013546.","journal-title":"J. Stat. Phys."},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1111\/j.1749-6632.1986.tb12450.x","volume":"480","author":"P Benioff","year":"1986","unstructured":"P. Benioff, Quantum mechanical hamiltonian models of computers, Annals New York Academy of Sciences 480 (1986), 475\u2013486.","journal-title":"Annals New York Academy of Sciences"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C Bennett","year":"1981","unstructured":"C. H. Bennett, J. Gill, Relative to a random oracle A, P\n A\n NP\n A\n # co -\n NP\n A, with probability one, SIAM J. Comput. 10 (1981), 96\u2013113.","journal-title":"SIAM J. Comput."},{"key":"1_CR12","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1038\/371479a0","volume":"371","author":"C Bennett","year":"1994","unstructured":"C. H. Bennett, Certainty from uncertainty, Nature 371 (1994), 694\u2013696.","journal-title":"Nature"},{"key":"1_CR13","first-page":"9","volume-title":"U. V. Vazirani","author":"C Bennett","year":"1995","unstructured":"C. H. Bennett, E. Bernstein, G. Brassard, U. V. Vazirani, Strength and weaknesses of quantum computing, Preprint, 1995, 9 pp."},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"765","DOI":"10.2307\/2023500","volume":"59","author":"P Benacerraf","year":"1962","unstructured":"P. Benacerraf, Tasks, super-tasks, and the modern eleatics, The Journal of Philosophy 59 (1962), 765\u2013784.","journal-title":"The Journal of Philosophy"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"E. Bernstein and U. Vazirani, Quantum complexity theory. In: Proc. 25th ACM Symp. on Theory of Computation, 1993, 11\u201320.","DOI":"10.1145\/167088.167097"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"A. Berthiaume and G. Brassard, The quantum challenge to structural complexity theory. In: Proc. 7th IEEE Conf. on Structure in Complexity Theory, 1992, 132\u2013137.","DOI":"10.1109\/SCT.1992.215388"},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M Blum","year":"1967","unstructured":"M. Blum, A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14 (1967), 322\u2013336.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR18","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1137\/S0097539793238140","volume":"23","author":"RV Book","year":"1995","unstructured":"R. V. Book, The complexity of languages reducible to algorithmically random languages, SIAM J. Comput. 23 (1995), 1275\u20131282.","journal-title":"SIAM J. Comput."},{"key":"1_CR19","first-page":"319","volume-title":"On complexity classes and algorithmically random languages, Proc. STACS-92, Lecture Notes Comp. Sci. 577","author":"RV Book","year":"1992","unstructured":"R. V. Book, J. Lutz, K. Wagner, On complexity classes and algorithmically random languages, Proc. STACS-92, Lecture Notes Comp. Sci. 577, Springer-Verlag, Berlin, 1992, 319\u2013328."},{"key":"1_CR20","volume-title":"Prentice Hall","author":"DP Bovet","year":"1984","unstructured":"D. P. Bovet, P. Crescenzi, Introduction to the Theory of Complexity, Prentice Hall, 1984."},{"key":"1_CR21","volume-title":"Computability \u2014A Mathematical Sketchbook","author":"DS Bridges","year":"1994","unstructured":"D. S. Bridges, Computability \u2014 A Mathematical Sketchbook, Springer-Verlag, Berlin, 1994."},{"key":"1_CR22","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/0304-3975(94)00050-6","volume":"132","author":"DS Bridges","year":"1994","unstructured":"D. S. Bridges, C. Calude, On recursive bounds for the exceptional values in speed-up, Theoret. Comput. Sci. 132 (1994), 387\u2013394.","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR23","volume-title":"Theories of Computational Complexity","author":"C Calude","year":"1988","unstructured":"C. Calude, Theories of Computational Complexity, North-Holland, Amsterdam, 1988."},{"key":"1_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03049-3","volume-title":"Information and Randomness \u2014 An Algorithmic Perspective","author":"C Calude","year":"1994","unstructured":"C. Calude, Information and Randomness \u2014 An Algorithmic Perspective, Springer-Verlag, Berlin, 1994."},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"C. Calude, D. I. Campbell, K. Svozil, D. *Stef\u00e1nescu, Strong determinism vs. computability. In: Proceedings of the International Symposium \u201cThe Foundational Debate\u201d, Vienna Circle Institute Yearbook, 3, 1995, Kluwer, Dordrecht, 115\u2013131.","DOI":"10.1007\/978-94-017-3327-4_9"},{"key":"1_CR26","first-page":"479","volume":"27","author":"C Calude","year":"1979","unstructured":"C. Calude, S. Marcus, Gh. P\u00e1un, The universal grammar as a hypothetical brain, Rev. Roumaine Ling. 27 (1979), 479\u2013489.","journal-title":"Rev. Roumaine Ling."},{"key":"1_CR27","first-page":"245","volume":"4","author":"C Calude","year":"1981","unstructured":"C. Calude, Gh. Nun, Global syntax and semantics for recursively enumerable languages, Fund. Inform. 4 (1981), 245\u2013254.","journal-title":"Fund. Inform."},{"key":"1_CR28","first-page":"343","volume":"27","author":"C Calude","year":"1982","unstructured":"C. Calude, Gh. P\u00e1un, On the adequacy of a grammatical model of the brain, Rev. Roumaine Ling. 27 (1982), 343\u2013351.","journal-title":"Rev. Roumaine Ling."},{"key":"1_CR29","unstructured":"C. Calude, S. Yu, Language-theoretic complexity of disjunctive sequences, Technical Report No 119, 1995,Department of Computer Science, The University of Auckland, New Zealand, 8 pp."},{"key":"1_CR30","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1080\/00207168408803423","volume":"16","author":"C Calude","year":"1984","unstructured":"C. Calude, M. Zimand, A relation between correctness and randomness in the computation of probabilistic algorithms, Internat. J. Comput. Math. 16 (1984), 47\u201353.","journal-title":"Internat. J. Comput. Math."},{"key":"1_CR31","first-page":"156","volume-title":"Effective category and measure in abstract complexity theory \u2014 extended abstract, Proceedings FCT\u201995, Lectures Notes in Computer Science 965","author":"C Calude","year":"1995","unstructured":"C. Calude, M. Zimand, Effective category and measure in abstract complexity theory \u2014 extended abstract, Proceedings FCT\u201995, Lectures Notes in Computer Science 965, Springer-Verlag, Berlin, 1995, 156\u2013171."},{"key":"1_CR32","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1103\/PhysRevA.48.116","volume":"48","author":"V Cern\u00ff","year":"1993","unstructured":"V. Cern\u00ff, Quantum computers and intractable (NP-complete) computing problems, Phys. Rev. 48 (1993), 116\u2013119.","journal-title":"Phys. Rev."},{"key":"1_CR33","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"GJ Chaitin","year":"1966","unstructured":"G. J. Chaitin, On the length of programs for computing finite binary sequences, J. Assoc. Comput. Mach. 13 (1966), 547\u2013569.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR34","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1145\/321832.321839","volume":"21","author":"GJ Chaitin","year":"1974","unstructured":"G. J. Chaitin, Information-theoretic limitations of formal systems, J. Assoc. Comput. Mach. 21 (1974), 403\u2013424.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR35","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"GJ Chaitin","year":"1975","unstructured":"G. J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329\u2013340.","journal-title":"J. Assoc. Comput. Mach"},{"key":"1_CR36","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1147\/rd.214.0350","volume":"21","author":"GJ Chaitin","year":"1977","unstructured":"G. J. Chaitin, Algorithmic information theory, IBM J. Res. Develop. 21 (1977), 350\u2013359.","journal-title":"IBM J. Res. Develop."},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"G. J. Chaitin, Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987 (third printing 1990 ).","DOI":"10.1017\/CBO9780511608858"},{"key":"1_CR38","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-1-4612-4808-8_28","volume-title":"Open Problems in Communication and Computation","author":"GJ Chaitin","year":"1987","unstructured":"G. J. Chaitin, Computing the Busy Beaver function. In: Cover, T. M. and Gopinath, B. (eds.), Open Problems in Communication and Computation, Springer-Verlag, Berlin, 1987, 108\u2013112."},{"key":"1_CR39","doi-asserted-by":"crossref","unstructured":"G. J. Chaitin, Information, Randomness and Incompleteness, Papers on Algorithmic Information Theory, World Scientific, Singapore, 1987 (second edition 1990 ).","DOI":"10.1142\/1048"},{"key":"1_CR40","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-3975(76)90005-0","volume":"2","author":"GJ Chaitin","year":"1976","unstructured":"G. J. Chaitin, Information-theoretic characterizations of recursive infinite strings, Theoret. Comput. Sci. 2 (1976), 45\u201348.","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR41","doi-asserted-by":"crossref","DOI":"10.1142\/1861","volume-title":"Information-Theoretic Incompleteness","author":"GJ Chaitin","year":"1992","unstructured":"G. J. Chaitin, Information-Theoretic Incompleteness, World Scientific, Singapore, 1992."},{"key":"1_CR42","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0096-3003(93)90037-F","volume":"59","author":"GJ Chaitin","year":"1993","unstructured":"G. J. Chaitin, On the number of N-bit strings with maximum complexity, Applied Mathematics and Computation 59 (1993), 97\u2013100.","journal-title":"Applied Mathematics and Computation"},{"key":"1_CR43","first-page":"198","volume":"57","author":"GJ Chaitin","year":"1995","unstructured":"G. J. Chaitin, A. Arslanov, C. Calude. Program-size complexity computes the halting problem, EATCS Bull., 57 (1995) 198\u2013200.","journal-title":"EATCS Bull"},{"key":"1_CR44","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1002\/cpa.3160310407","volume":"31","author":"GJ Chaitin","year":"1978","unstructured":"G. J. Chaitin, J. T. Schwartz, A note on Monte-Carlo primality tests and algorithmic information theory, Comm. Pure Appl. Math. 31 (1978), 521\u2013527.","journal-title":"Comm. Pure Appl. Math."},{"key":"1_CR45","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"A. K. Chandra, D. C. Kozen, L. J. Stockmeyer, Alternation, J. Assoc. Comput. Mach. 28 (1981), 114\u2013133.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR46","unstructured":"A. Cobham, The intrinsic computational difficulty of functions. In: Proc. Congress for Logic, Mathematics, and Philosophy of Science 1964, 24\u201330."},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem proving procedure. In: Proc. 3-rd Annual ACM STOC, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"S. A. Cook, An observation on time-storage trade off. In: Proc. 5-th Annual ACM STOC, 1973, 29\u201333.","DOI":"10.1145\/800125.804032"},{"key":"1_CR49","doi-asserted-by":"crossref","unstructured":"S. A. Cook, Deterministic CFL\u2019s are accepted simultaneously in polynomial time and log squared space. In: Proc. ACM STOC\u201979,338\u2013345.","DOI":"10.1145\/800135.804426"},{"key":"1_CR50","first-page":"568","volume-title":"Handbook of Mathematical Logic","author":"M Davis","year":"1976","unstructured":"M. Davis, Unsolvable problems. In: Barwise, J. (ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam, 1976, 568\u2013594."},{"key":"1_CR51","volume-title":"The Mind of God, Science and the Search for Ultimate Meaning","author":"P Davies","year":"1992","unstructured":"P. Davies, The Mind of God, Science and the Search for Ultimate Meaning, Penguin Books, London, 1992."},{"key":"1_CR52","first-page":"97","volume":"400","author":"D Deutsch","year":"1985","unstructured":"D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proceedings of the Royal Society of London 400 (1985), 97\u2013117.","journal-title":"Proceedings of the Royal Society of London"},{"key":"1_CR53","first-page":"73","volume":"425","author":"D Deutsch","year":"1989","unstructured":"D. Deutsch, Quantum computational networks, Proceedings of the Royal Society of London 425 (1989), 73\u201390.","journal-title":"Proceedings of the Royal Society of London"},{"key":"1_CR54","first-page":"553","volume":"439","author":"D Deutsch","year":"1992","unstructured":"D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proceedings of the Royal Society of London 439 (1992), 553\u2013558","journal-title":"Royal Society of London"},{"key":"1_CR55","unstructured":"R. L. Devaney, An Introduction to Chaotic Dynamical Systems, AddisonWessley, 1989."},{"key":"1_CR56","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1086\/289716","volume":"60","author":"J Earman","year":"1993","unstructured":"J. Earman and J. D. Norton, Forever is a day: supertasks in Pitowsky and Malament-Hogarth spacetimes, Philosophy of Science 60 (1993), 22\u201342.","journal-title":"Philosophy of Science"},{"key":"1_CR57","volume-title":"LOeuvre ouverte","author":"U Eco","year":"1965","unstructured":"U. Eco, L\u2019Oeuvre ouverte, Editions du Seuil, Paris, 1965."},{"key":"1_CR58","unstructured":"G.M. Edelman, Bright Air, Brilliant Fire \u2014 On the Matter of Mind, Basic Books, 1992."},{"key":"1_CR59","volume-title":"Kurt G\u00f6del Collected Works","year":"1986","unstructured":"S. Feferman, J. Dawson, Jr., S. C. Kleene, G. H. Moore, R. M. Solovay, J. van Heijenoort (eds.), Kurt G\u00f6del Collected Works, Volume I, Oxford University Press, New York, 1986."},{"key":"1_CR60","volume-title":"Kurt G\u00f6del Collected Works","year":"1990","unstructured":"S. Feferman, J. Dawson, Jr., S.C. Kleene, G. H. Moore, R. M. Solovay, J. van Heijenoort (eds.), Kurt G\u00f6del Collected Works, Volume II, Oxford University Press, New York, 1990."},{"key":"1_CR61","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"RP Feynman","year":"1982","unstructured":"R. P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics 21 (1982), 467\u2013488.","journal-title":"International Journal of Theoretical Physics"},{"key":"1_CR62","first-page":"1120","volume":"11","author":"R. P. Feynman","year":"1985","unstructured":"R. P. Feynman, Quantum Mechanical Computers, Opt. News 11 (1985), 1120.","journal-title":"News"},{"key":"1_CR63","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(86)80004-3","volume":"70","author":"P G\u00e1cs","year":"1986","unstructured":"P. G\u00e1cs, Every sequence is reducible to a random one, Inform. and Control 70 (1986), 186\u2013192.","journal-title":"Inform. and Control"},{"key":"1_CR64","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979."},{"key":"1_CR65","unstructured":"M. Gardner, Logic Machines and Diagrams, University of Chicago Press, Chicago, 1958, 144 (second printing, Harvester Press, 1983 )."},{"key":"1_CR66","first-page":"133","volume-title":"Fractal Music, Hypercards, and More","author":"M Gardner","year":"1992","unstructured":"M. Gardner, Fractal Music, Hypercards, and More..., W. H. Freeman, New York, 1992, 133."},{"key":"1_CR67","doi-asserted-by":"crossref","unstructured":"V. Geffert, Bridging across the log(n) space frontier. In: Proc. MFCS\u201995, Lect. Notes Comp. Sci. 969, Springer-Verlag, 1995, 50\u201365.","DOI":"10.1007\/3-540-60246-1_112"},{"key":"1_CR68","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J Gill","year":"1977","unstructured":"J. Gill, Computational complexity of probabilistic Turing machines, SIAM J. Computing 6 (1977), 675\u2013695.","journal-title":"SIAM J. Computing"},{"key":"1_CR69","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"LM Goldschlager","year":"1982","unstructured":"L. M. Goldschlager, A universal interconnection pattern for parallel computers, J. Assoc. Comput. Mach. 29 (1982), 1073\u20131086.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR70","volume-title":"The Self-Aware Universe \u2014 How Consciouness Creates the Material World","author":"A Goswami","year":"1993","unstructured":"A. Goswami, R. E. Reed, M. Goswami, The Self-Aware Universe \u2014 How Consciouness Creates the Material World, G. P. Putnam\u2019s Sons, New York, 1993."},{"key":"1_CR71","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computations","author":"R Greenlaw","year":"1995","unstructured":"R. Greenlaw, H. J. Hoover, W. L. Ruzzo, Limits to Parallel Computations, Oxford University Press, Oxford, 1995."},{"key":"1_CR72","unstructured":"A. Gr\u00fcnbaum, Modern Science and Zeno\u2019s paradoxes, Allen and Unwin, London, 1968 (second edition)."},{"key":"1_CR73","doi-asserted-by":"crossref","unstructured":"A. Gr\u00fcnbaum, Philosophical Problems of Space of Time,D. Reidel, Dordrecht, 1973. (second, enlarged edition)","DOI":"10.1007\/978-94-010-2622-2"},{"key":"1_CR74","volume-title":"Tilings and Patterns","author":"B Gr\u00fcmbaum","year":"1987","unstructured":"B. Gr\u00fcmbaum, G. C. Shephard, Tilings and Patterns, W. H. Freeman, New York, 1987."},{"key":"1_CR75","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1008335.1008336","volume":"8","author":"J Hartmanis","year":"1976","unstructured":"J. Hartmanis, J. E. Hoperoft, Independence results in computer science, SIGACT News 8 (1976), 13\u201324.","journal-title":"SIGACT News"},{"key":"1_CR76","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/321650.321661","volume":"18","author":"J Hartmanis","year":"1971","unstructured":"J. Hartmanis, J. E. Hoperoft, An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18 (1971), 444\u2013475.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR77","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, P. M. Lewis II, R. E. Stearns, Hierarchies of memory limited computations. In: Proc. 6th Annual IEEE Symp. on Switching Circuit Theory and Logical Design, 1965, 179\u2013190.","DOI":"10.1109\/FOCS.1965.11"},{"key":"1_CR78","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"J. Hartmanis, R. E. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285\u2013306.","journal-title":"Trans. Amer. Math. Soc"},{"key":"1_CR79","unstructured":"D. Havel, Algorithmics: The Spirit of Computing, Addison-Wesley, 1987."},{"key":"1_CR80","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"FC Hennie","year":"1966","unstructured":"F. C. Hennie, R. E. Stearns, Two-tape simulation of multitape Turing machines, J. Assoc. Comput. Mach. 13 (1966), 533\u2013546.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR81","doi-asserted-by":"crossref","unstructured":"M. Hogarth, Non-Turing computers and non-Turing computability, PSA\n 1994 1 (1994), 126\u2013138.","DOI":"10.1086\/psaprocbienmeetp.1994.1.193018"},{"key":"1_CR82","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"JE Hoperoft","year":"1977","unstructured":"J. E. Hoperoft, J. W. Paul, L. Valiant, On time versus space, J. Assoc. Comput. Mach. 24 (1977), 332\u2013337.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR83","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1145\/321466.321474","volume":"15","author":"JE Hoperoft","year":"1968","unstructured":"J. E. Hoperoft, J. D. Ullman, Relations between time and tape complexities, J. Assoc. Comput. Mach. 15 (1968), 414\u2013427.","journal-title":"J. Assoc. Comput. Mach"},{"key":"1_CR84","unstructured":"J. E. Hoperoft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979."},{"key":"1_CR85","unstructured":"J. Hromkovic, How to organize communication among parallel processes in alternating computations, Unpublished manuscript, Comenius University, Bratislava, January 1986."},{"key":"1_CR86","unstructured":"J. Hromkovic, Communication Complexity and Parallel Computing,EATCS Texts in Theoretical Computer Science, in preparation."},{"key":"1_CR87","unstructured":"J. Hromkovic, O. H. Ibarra, N. Q. Tr\u00e1n, P, NP and PSPACE characterizations by synchronized alternating finite automata with different communication protocols, Unpublished manuscript, 1994."},{"key":"1_CR88","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0304-3975(94)90103-1","volume":"127","author":"J Hromkovic","year":"1994","unstructured":"J. Hromkovic, J. Kari, L. Kari, Some hierarchies for the communication complexity measures of cooperating grammar systems, Theoretical Computer Science 127 (1994), 123\u2013147.","journal-title":"Theoretical Computer Science"},{"key":"1_CR89","first-page":"423","volume-title":"Proc. 19th MFCS94, Lect. Notes Comp. Sci","author":"J Hromkovic","year":"1994","unstructured":"J. Hromkovic, J. Kari, L. Kari, D. Pardubsk\u00e1, Two lower bounds on distributive generation of languages. In: Proc. 19th MFCS\u201994, Lect. Notes Comp. Sci. 841, Springer-Verlag, Berlin, 1994, 423\u2013432."},{"key":"1_CR90","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0166-218X(91)90098-H","volume":"32","author":"J Hromkovic","year":"1991","unstructured":"J. Hromkovic, J. Karhum\u00e4ki, B. Rovan, and A. Slobodov\u00e1, On the power of synchronization in parallel computations, Disc. Appl. Math. 32 (1991), 156\u2013182.","journal-title":"Disc. Appl. Math."},{"key":"1_CR91","doi-asserted-by":"crossref","unstructured":"J. Hromkovic, R. Klasing, B. Monien, R. Peine, Dissemination of information in interconnection networks (broadcasting and gossiping). In: Hsu, F., Du, D.-Z. eds., Combinatorial Network Theory,Science Press andAMS 1995, to appear.","DOI":"10.1007\/978-1-4757-2491-2_5"},{"key":"1_CR92","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0304-3975(94)90238-0","volume":"132","author":"J Hromkovic","year":"1994","unstructured":"J. Hromkovic, B. Rovan, A. Slobodov\u00e1, Deterministic versus nondeterministic space in terms of synchronized alternating machines, Theoret. Comp. Sci. 132 (1994), 319\u2013336.","journal-title":"Theoret. Comp. Sci."},{"key":"1_CR93","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01178509","volume":"31","author":"OH Ibarra","year":"1994","unstructured":"O. H. Ibarra, N. Q. Tr\u00e1n, On communication-bounded synchronized alternating finite automata, Acta Informatica 31 (1994), 315\u2013327.","journal-title":"Acta, Informatica"},{"key":"1_CR94","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N Immerman","year":"1988","unstructured":"N. Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput. 17 (1988), 935\u2013938.","journal-title":"SIAM J. Comput."},{"key":"1_CR95","first-page":"67","volume-title":"Handbook of Theoretical Computer Science","author":"DS Johnson","year":"1990","unstructured":"D. S. Johnson, A catalog of complexity classes. In: van Leeuwen, J. (ed.), Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam, 1990, 67\u2013161."},{"key":"1_CR96","unstructured":"H. J\u00fcrgensen, G. Thierrin, Some structural properties of w-languages, 13th Nat. School with Internat. Participation \u201cApplications of Mathematics in Technology\u201d, Sofia, 1988, 56\u201363."},{"key":"1_CR97","first-page":"506","volume-title":"Proc. 8-th ICALP81, Lect. Notes Comp. Sci","author":"KN King","year":"1981","unstructured":"K. N. King, Alternating multihead finite automata. In: Proc. 8-th ICALP\u201981, Lect. Notes Comp. Sci. 115, Springer-Verlag, Berlin, 1981, 506\u2013520."},{"key":"1_CR98","first-page":"191","volume":"20","author":"LG Khachiyan","year":"1979","unstructured":"L. G. Khachiyan, A polynomial algorithm in linear programming, Soviet Mathematics Doklad 20 (1979), 191\u2013194.","journal-title":"Soviet Mathematics Doklad"},{"key":"1_CR99","first-page":"3","volume":"1","author":"AN Kolmogorov","year":"1965","unstructured":"A. N. Kolmogorov, Three approaches for defining the concept of \u201cinformation quantity\u201d, Problems Inform. Transmission 1 (1965), 3\u201311.","journal-title":"Problems Inform. Transmission"},{"key":"1_CR100","unstructured":"K.-J. Lange, Complexity and Structure in Formal Language Theory. Unpublished manuscript,University of T\u00fcbingen, Germany"},{"key":"1_CR101","volume-title":"A Philosophical Essay on Probability Theories","author":"PS Laplace","year":"1951","unstructured":"P. S. Laplace, A Philosophical Essay on Probability Theories, Dover, New York, 1951."},{"key":"1_CR102","volume-title":"Introduction to Parallel Algorithms and Architectures: Array Trees Hypercubes, Morgan Kaufmann Publishers","author":"FT Leighton","year":"1992","unstructured":"F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Array Trees Hypercubes, Morgan Kaufmann Publishers, San Mateo, California, 1992."},{"key":"1_CR103","first-page":"206","volume":"10","author":"LA Levin","year":"1974","unstructured":"L. A. Levin, Randomness conservation inequalities: information and independence in mathematical theories, Problems Inform. Transmission 10 (1974), 206\u2013210.","journal-title":"Problems Inform. Transmission"},{"key":"1_CR104","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/S009753979324485X","volume":"24","author":"M Li","year":"1995","unstructured":"M. Li, P. M. Vit\u00e1nyi, A new approach to formal language theory by Kolmogorov complexity, SIAM J. Comput. 24 (1995), 398\u2013410.","journal-title":"SIAM J. Comput."},{"key":"1_CR105","volume-title":"About Two Communication Structures of PCGS, Master Thesis, Dept. of Computer Science","author":"M Luk\u00e1c","year":"1992","unstructured":"M. Luk\u00e1c, About Two Communication Structures of PCGS, Master Thesis, Dept. of Computer Science, Comenius University, Bratislava, 1992."},{"key":"1_CR106","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"JH Lutz","year":"1992","unstructured":"J. H. Lutz, Almost everywhere high nonuniform complexity, J. Comput. System Sci. 44 (1992), 220\u2013258.","journal-title":"J. Comput. System Sci."},{"key":"1_CR107","doi-asserted-by":"crossref","unstructured":"J. H. Lutz, The quantitative structure of exponential time, Proceedings of the Eighth Annual Structure in Complexity Theory Conference, (San Diego, CA, May 18\u201321, 1993), IEEE Computer Society Press, 1993, 158\u2013175.","DOI":"10.1109\/SCT.1993.336530"},{"key":"1_CR108","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P Martin-L\u00f6f","year":"1966","unstructured":"P. Martin-L\u00f6f, The definition of random sequences, Inform. and Control 9 (1966), 602\u2013619.","journal-title":"Inform. and Control"},{"key":"1_CR109","volume-title":"Hilbert\u2019s Tenth Problem","author":"P Martin-L\u00f6f","year":"1993","unstructured":"Yu. V. Matiyasevich, Hilbert\u2019s Tenth Problem, MIT Press, Cambridge, Massachusetts, London, 1993."},{"key":"1_CR110","doi-asserted-by":"crossref","first-page":"219","DOI":"10.2307\/1576055","volume":"27","author":"MM France","year":"1994","unstructured":"M. Mend\u00e8s France, A. H\u00e9naut, Art, therefore entropy, Leonardo 27 (1994), 219\u2013221.","journal-title":"Leonardo"},{"key":"1_CR111","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"13","author":"GL Miller","year":"1976","unstructured":"G. L. Miller, Riemann\u2019s hypothesis and tests for primality, J. Comput. Syst. Sci. 13 (1976), 300\u2013317.","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR112","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-7091-9076-0_13","volume":"7","author":"B Monien","year":"1990","unstructured":"B. Monien, I. H. Sudborough, Embedding one interconnection network in another, Computing Suppl. 7 (1990), 257\u2013282.","journal-title":"Computing Suppl"},{"key":"1_CR113","unstructured":"C. Moore, Real-valued, continuous-time computers: a model of analog computation, Part I, Manuscript, 1995, 15 pp."},{"key":"1_CR114","unstructured":"P. Odifreddi, Classical Recursion Theory, North-Holland, Amsterdam, Vol. 1, 1989."},{"key":"1_CR115","volume-title":"The Dreams of Reason","author":"HR Pagels","year":"1989","unstructured":"H. R. Pagels, The Dreams of Reason, Bantam Books, New York, 1989."},{"key":"1_CR116","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"C. H. Papadimitriou, Computational Complexity, Addison-Wesley, New York, 1994."},{"key":"1_CR117","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"C Papadimitriou","year":"1984","unstructured":"Ch. Papadimitriou, M. Sipser, Communication complexity, J. Comp. Syst. Sci. 28 (1984), 260\u2013269.","journal-title":"J. Comp. Syst. Sci."},{"key":"1_CR118","unstructured":"D. Pardubsk\u00e1, On the Power of Communication Structure for Distributive Generation of Languages, Ph.D. Thesis, Comenius University, Bratislava 1994."},{"key":"1_CR119","first-page":"55","volume":"37","author":"G P\u00e1un","year":"1989","unstructured":"Gh. P\u00e1un, L. S\u00e1ntean, Parallel communicating grammar systems: The regular case, Ann. Univ. Buc. Ser. Mat.-Inform. 37 (1989), 55\u201363.","journal-title":"Ann. Univ. Buc. Ser. Mat.-Inform."},{"key":"1_CR120","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198519737.001.0001","volume-title":"The Emperors New Mind. Concerning Computers, Minds, and the Laws of Physics","author":"R Penrose","year":"1989","unstructured":"R. Penrose, The Emperor\u2019s New Mind. Concerning Computers, Minds, and the Laws of Physics, Oxford University Press, Oxford, 1989."},{"key":"1_CR121","volume-title":"Shadows of the Mind. A Search for the Missing Science of Consciousness","author":"R Penrose","year":"1994","unstructured":"R. Penrose, Shadows of the Mind. A Search for the Missing Science of Consciousness, Oxford University Press, Oxford, 1994."},{"key":"1_CR122","first-page":"307","volume-title":"Proc. 20th IEEE Symp. FOCS","author":"N Pipinger","year":"1979","unstructured":"N. Pipinger, On simultaneous resource bounds (preliminary version). In: Proc. 20th IEEE Symp. FOCS, IEEE, New York 1979, 307\u2013311."},{"key":"1_CR123","first-page":"81","volume":"39","author":"I Pitowsky","year":"1990","unstructured":"I. Pitowsky, The physical Church-Turing thesis and physical complexity theory, Iyyun, A Jerusalem Philosophical Quarterly 39 (1990), 81\u201399.","journal-title":"Iyyun, A Jerusalem Philosophical Quarterly"},{"key":"1_CR124","first-page":"21","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"MO Rabin","year":"1976","unstructured":"M. O. Rabin, Probabilistic algorithms. In: Traub, J., ed., Algorithms and Complexity: New Directions and Recent Results, Academic Press, New York, 1976, 21\u201340."},{"key":"1_CR125","unstructured":"G. Rozenberg, A. Salomaa, Cornerstones of Undecidability, Prentice Hall, 1994."},{"key":"1_CR126","volume-title":"Infinity and the Mind","author":"R Rucker","year":"1983","unstructured":"R. Rucker, Infinity and the Mind, Bantam Books, New York, 1983."},{"key":"1_CR127","volume-title":"Mind Tools","author":"R Rucker","year":"1987","unstructured":"R. Rucker, Mind Tools, Houghton Mifflin, Boston, 1987."},{"key":"1_CR128","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107325630","volume-title":"Computation and Automata","author":"A Salomaa","year":"1985","unstructured":"A. Salomaa, Computation and Automata, Cambridge University Press, Cambridge, 1985."},{"key":"1_CR129","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities, J. Comp. Syst. Sciences 4 (1970), 177\u2013192.","journal-title":"J. Comp. Syst. Sciences"},{"key":"1_CR130","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5834.001.0001","volume-title":"The Rediscovery of the Mind","author":"JR Searle","year":"1992","unstructured":"J. R. Searle, The Rediscovery of the Mind, MIT Press, Cambridge, Mass. (third printing 1992)."},{"key":"1_CR131","unstructured":"P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring. In: Proc. 35th Annual IEEE FOCS,IEEE, 1995 (in press)."},{"key":"1_CR132","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1126\/science.268.5210.545","volume":"268","author":"HT Siegelmann","year":"1995","unstructured":"H. T. Siegelmann, Computation beyond the Turing limit, Science 268 (1995), 545\u2013548.","journal-title":"Science"},{"key":"1_CR133","first-page":"518","volume-title":"Proc. 13th MFCS88, Lect. Notes Comp. Sci","author":"A Slobodov\u00e1","year":"1988","unstructured":"A. Slobodov\u00e1, On the power of communication in alternating machines. In: Proc. 13th MFCS\u201988, Lect. Notes Comp. Sci. 324, Springer-Verlag, Berlin, 1988, 518\u2013528."},{"key":"1_CR134","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198534501.001.0001","volume-title":"Diagonalization and Self-Reference","author":"RM Smullyan","year":"1994","unstructured":"R. M. Smullyan, Diagonalization and Self-Reference, Clarendon Press, Oxford, 1994."},{"key":"1_CR135","first-page":"215","volume-title":"Draft of a paper (or series of papers) on Chaitin\u2019s work... done for the most part during the period of Sept.-Dec. 1974","author":"RM Solovay","year":"1975","unstructured":"R. M. Solovay, Draft of a paper (or series of papers) on Chaitin\u2019s work... done for the most part during the period of Sept.-Dec. 1974, unpublished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp."},{"key":"1_CR136","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R Solovay","year":"1977","unstructured":"R. Solovay, V. Strassen, A fast Monte Carlo test for primality, SIAM J. Computing 6 (1977), 84\u201385.","journal-title":"SIAM J. Computing"},{"key":"1_CR137","volume-title":"Minimalism \u2014 Origins","author":"E Strickland","year":"1993","unstructured":"E. Strickland, Minimalism \u2014 Origins, Indiana University Press, Bloomington, 1993."},{"key":"1_CR138","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi, The method of forced enumeration for nondeterministic automata, Acta Informatica 26 (1988), 279\u2013284.","journal-title":"Acta Informatica"},{"key":"1_CR139","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-58355-6","volume-title":"Turing Machines with Sublogarithmic Space, Lect. Notes Comp. Sci","author":"A Szepietowski","year":"1994","unstructured":"A. Szepietowski, Turing Machines with Sublogarithmic Space, Lect. Notes Comp. Sci. 843, Springer-Verlag, Berlin, 1994."},{"key":"1_CR140","doi-asserted-by":"crossref","DOI":"10.1142\/1524","volume-title":"Randomness and Undecidability in Physics","author":"K Svozil","year":"1993","unstructured":"K. Svozil, Randomness and Undecidability in Physics, World Scientific, Singapore, 1993."},{"key":"1_CR141","first-page":"834","volume-title":"Fundamental Problems in Quantum Theory: A Conference Held in Honor of Professor John A. Wheeler, Annals of the New York Academy of Sciences","author":"K Svozil","year":"1995","unstructured":"K. Svozil, On the computational power of physical systems, undecidability, the consistency of phenomena and the practical uses of paradoxes. In: Greenberger, D. M., Zeilinger, A. (eds.), Fundamental Problems in Quantum Theory: A Conference Held in Honor of Professor John A. Wheeler, Annals of the New York Academy of Sciences 755 (1995), 834\u2013842."},{"key":"1_CR142","first-page":"170","volume":"55","author":"K Svozil","year":"1995","unstructured":"K. Svozil, Quantum computation and complexity theory, I, EATCS Bull. 55 (1995), 170\u2013207.","journal-title":"EATCS Bull"},{"key":"1_CR143","first-page":"116","volume":"56","author":"K Svozil","year":"1995","unstructured":"K. Svozil, Quantum computation and complexity theory, II, EATCS Bull. 56 (1995), 116\u2013136.","journal-title":"EATCS Bull"},{"key":"1_CR144","first-page":"230","volume":"242","author":"AM Turing","year":"1936","unstructured":"A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. Ser. 242 (1936), 230\u2013265.","journal-title":"Proc. London Math. Soc. Ser."},{"key":"1_CR145","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/analys\/15.1.1","volume":"15","author":"JF Thomson","year":"1954","unstructured":"J. F. Thomson, Tasks and super-tasks, Analysis 15 (1954), 1\u201313.","journal-title":"Analysis"},{"key":"1_CR146","volume-title":"Philosophy of Mathematics and Natural Science","author":"H Weyl","year":"1949","unstructured":"H. Weyl, Philosophy of Mathematics and Natural Science, Princeton University Press, Princeton, 1949."},{"issue":"4","key":"1_CR147","first-page":"10","volume":"253","author":"I Xenakis","year":"1963","unstructured":"I. Xenakis, Musique formelle, La Revue Musicale 253 \/4 (1963), 10.","journal-title":"La Revue Musicale"},{"key":"1_CR148","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Some complexity questions related to distributed computing. In: Proc. 11th Annual ACM STOC, ACM 1981, 308\u2013311.","DOI":"10.1145\/800076.802483"},{"key":"1_CR149","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0020-0190(89)90108-7","volume":"31","author":"S Yu","year":"1989","unstructured":"S. Yu, A pumping lemma for deterministic context-free languages, Inform. Process. Lett. 31 (1989), 47\u201351.","journal-title":"Inform. Process. Lett"},{"key":"1_CR150","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(93)90161-L","volume":"119","author":"M Zimand","year":"1993","unstructured":"M. Zimand, If not empty, NP \u2014 P is topologically large, Theoret. Comput. Sci. 119 (1993), 293\u2013310.","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR151","first-page":"525","volume-title":"Handbook of Theoretical Computer Science, Vol","author":"BP Emde","year":"1990","unstructured":"P. van Emde Boas, Machine models and simulations. In: van Leeuwen, J. (ed.), Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam, 1990, 525\u2013632."},{"key":"1_CR152","volume-title":"How to Prove It. A Structural Approach","author":"DJ Velleman","year":"1994","unstructured":"D. J. Velleman, How to Prove It. A Structural Approach, Cambridge University Press, Cambridge, 1994."},{"key":"1_CR153","first-page":"161","volume-title":"Natures Imagination","author":"H Wang","year":"1995","unstructured":"H. Wang, On \u2018computabilism\u2019 and physicalism: some subproblems. In: Cornwell, J., (ed.), Nature\u2019s Imagination, Oxford University Press, Oxford, 1995, 161\u2013189."}],"container-title":["Handbook of Formal Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-07675-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T12:22:05Z","timestamp":1768220525000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-07675-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783642082306","9783662076750"],"references-count":153,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-07675-0_1","relation":{},"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"26 March 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}