{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T05:29:06Z","timestamp":1736573346080,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055756","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T17:36:31Z","timestamp":1155836191000},"page":"36-53","source":"Crossref","is-referenced-by-count":6,"title":["Towards a theory of recursive structures"],"prefix":"10.1007","author":[{"given":"David","family":"Harel","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"3_CR1","first-page":"209","volume-title":"Generic Computation and Its Complexity","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu, \u201cGeneric Computation and Its Complexity\u201d, Proc. 23rd Ann. ACM Symp. on Theory of Computing, pp. 209\u2013219, ACM Press, New York, 1991."},{"issue":"2","key":"3_CR2","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0095-8956(92)90057-5","volume":"54","author":"R. Aharoni","year":"1992","unstructured":"R. Aharoni, M. Magidor and R. A. Shore, \u201cOn the Strength of K\u00f6nig's Duality Theorem\u201d, J. of Combinatorial Theory (Series B) 54:2 (1992), 257\u2013290.","journal-title":"J. of Combinatorial Theory (Series B)"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"469","DOI":"10.2307\/2272247","volume":"41","author":"D.R. Bean","year":"1976","unstructured":"D.R. Bean, \u201cEffective Coloration\u201d, J. Sym. Logic 41 (1976), 469\u2013480.","journal-title":"J. Sym. Logic"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"385","DOI":"10.2307\/2041731","volume":"55","author":"D.R. Bean","year":"1976","unstructured":"D.R. Bean, \u201cRecursive Euler and Hamiltonian Paths\u201d, Proc. Amer. Math. Soc. 55 (1976), 385\u2013394.","journal-title":"Proc. Amer. Math. Soc."},{"key":"3_CR5","unstructured":"R. Beigel and W. I. Gasarch, unpublished results, 1986\u20131990."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(89)90029-8","volume":"45","author":"R. Beigel","year":"1989","unstructured":"R. Beigel and W. I. Gasarch, \u201cOn the Complexity of Finding the Chromatic Number of a Recursive Graph\u201d, Parts I & II, Ann. Pure and Appl. Logic 45 (1989), 1\u201338, 227\u2013247.","journal-title":"Ann. Pure and Appl. Logic"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0012-365X(84)90046-3","volume":"50","author":"S. A. Burr","year":"1984","unstructured":"S. A. Burr, \u201cSome Undecidable Problems Involving the Edge-Coloring and Vertex Coloring of Graphs\u201d, Disc. Math. 50 (1984), 171\u2013177.","journal-title":"Disc. Math."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. K. Chandra","year":"1980","unstructured":"A. K. Chandra and D. Harel, \u201cComputable Queries for Relational Data Bases\u201d, J. Comp. Syst. Sci. 21, (1980), 156\u2013178.","journal-title":"J. Comp. Syst. Sci."},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A.K. Chandra","year":"1982","unstructured":"A.K. Chandra and D. Harel, \u201cStructure and Complexity of Relational Queries\u201d, J. Comput. Syst. Sci. 25 (1982), 99\u2013128.","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR10","unstructured":"R. Fagin, \u201cGeneralized First-Order Spectra and Polynomial-Time Recognizable Sets\u201d, In Complexity of Computations (R. Karp, ed.), SIAM-AMS Proceedings, Vol. 7, 1974, pp. 43\u201373."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/2272945","volume":"41","author":"R. Fagin","year":"1976","unstructured":"R. Fagin, \u201cProbabilities on Finite Models\u201d, J. of Symbolic Logic, 41, (1976), 50\u201358.","journal-title":"J. of Symbolic Logic"},{"key":"3_CR12","unstructured":"W.I. Gasarch and M. Lockwood, \u201cThe Existence of Matchings for Recursive and Highly Recursive Bipartite Graphs\u201d, Technical Report 2029, Univ. of Maryland, May 1988."},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/BF01071084","volume":"5","author":"Y. V. Glebskii","year":"1969","unstructured":"Y. V. Glebskii, D. I. Kogan, M. I. Liogonki and V. A. Talanov, \u201cRange and Degree of Realizability of Formulas in the Restricted Predicate Calculus\u201d, Cybernetics 5, (1969), 142\u2013154.","journal-title":"Cybernetics"},{"issue":"3","key":"3_CR14","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/BF02773868","volume":"76","author":"D. Harel","year":"1991","unstructured":"D. Harel, \u201cHamiltonian Paths in Infinite Graphs\u201d, Israel J. Math. 76:3 (1991), 317\u2013336. (Also, Proc. 23rd Ann. ACM Symp. on Theory of Computing, New Orleans, pp. 220\u2013229, 1991.)","journal-title":"Israel J. Math."},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"T. Hirst and D. Harel, \u201cTaking it to the Limit: On Infinite Variants of NP-Complete Problems\u201d, J. Comput. Syst. Sci., to appear. (Also, Proc. 8th IEEE Conf. on Structure in Complexity Theory, IEEE Press, New York, 1993, pp. 292\u2013304.)","DOI":"10.1109\/SCT.1993.336518"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"T. Hirst and D. Harel, \u201cCompleteness Results for Recursive Data Bases\u201d, J. Comput. Syst. Sci., to appear. (Also, 12th ACM Ann. Symp. on Principles of Database Systems, ACM Press, New York, 1993, 244\u2013252.)","DOI":"10.1145\/153850.153905"},{"key":"3_CR17","unstructured":"T. Hirst and D. Harel, \u201cMore about Recursive Structures: Zero-One Laws and Expressibility vs. Complexity\u201d, in preparation."},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, \u201cRelational Queries Computable in Polynomial Time\u201d, Inf. and Cont. 68 (1986), 86\u2013104.","journal-title":"Inf. and Cont."},{"key":"3_CR19","unstructured":"P. G. Kolaitis and M. N. Thakur, \u201cLogical definability of NP optimization problems\u201d, 6th IEEE Conf. on Structure in Complexity Theory, pp. 353\u2013366, 1991."},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1112\/plms\/s3-25.4.615","volume":"3","author":"A. Manaster","year":"1972","unstructured":"A. Manaster and J. Rosenstein, \u201cEffective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)\u201d, Proc. London Math. Soc. 3 (1972), 615\u2013654.","journal-title":"Proc. London Math. Soc."},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BF02260930","volume":"32","author":"A. S. Morozov","year":"1993","unstructured":"A. S. Morozov, \u201cFunctional Trees and Automorphisms of Models\u201d, Algebra and Logic 32 (1993), 28\u201338.","journal-title":"Algebra and Logic"},{"key":"3_CR22","unstructured":"Y. N. Moschovakis, Elementary Induction on Abstract Structures, North Holland, 1974."},{"key":"3_CR23","first-page":"323","volume-title":"Recursion Theory, Proc. Symp. in Pure Math. Vol. 42","author":"A. Nerode","year":"1985","unstructured":"A. Nerode and J. Remmel, \u201cA Survey of Lattices of R. E. Substructures\u201d, In Recursion Theory, Proc. Symp. in Pure Math. Vol. 42 (A. Nerode and R. A. Shore, eds.), Amer. Math. Soc., Providence, R. I., 1985, pp. 323\u2013375."},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0304-3975(93)90259-V","volume":"107","author":"A. Panconesi","year":"1993","unstructured":"A. Panconesi and D. Ranjan, \u201cQuantifiers and Approximation\u201d, Theor. Comp. Sci. 107 (1993), 145\u2013163.","journal-title":"Theor. Comp. Sci."},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis, \u201cOptimization, Approximation, and Complexity Classes\u201d, J. Comp. Syst. Sci. 43, (1991), 425\u2013440.","journal-title":"J. Comp. Syst. Sci."},{"key":"3_CR26","doi-asserted-by":"crossref","first-page":"331","DOI":"10.4064\/aa-9-4-331-340","volume":"9","author":"R. Rado","year":"1964","unstructured":"R. Rado, \u201cUniversal Graphs and Universal Functions\u201d, Acta Arith., 9, (1964), 331\u2013340.","journal-title":"Acta Arith."},{"key":"3_CR27","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1967","unstructured":"H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967."},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi, \u201cThe Complexity of Relational Query Languages\u201d, Proc. 14th ACM Ann. Symp. on Theory of Computing, 1982, pp. 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T13:52:39Z","timestamp":1736517159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/bfb0055756","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}