{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T00:10:19Z","timestamp":1742602219725,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540630456"},{"type":"electronic","value":"9783540690658"}],"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\/3-540-63045-7_15","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:00:03Z","timestamp":1330297203000},"page":"141-144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards a theory of recursive structures"],"prefix":"10.1007","author":[{"given":"David","family":"Harel","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,25]]},"reference":[{"issue":"2","key":"15_CR1","doi-asserted-by":"crossref","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":"15_CR2","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1017\/S0022481200051549","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":"15_CR3","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1090\/S0002-9939-1976-0416888-0","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."},{"unstructured":"R. Beigel and W. I. Gasarch, unpublished results, 1986\u20131990.","key":"15_CR4"},{"key":"15_CR5","doi-asserted-by":"crossref","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":"15_CR6","doi-asserted-by":"crossref","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":"15_CR7","doi-asserted-by":"crossref","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."},{"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":"15_CR8"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1017\/S0022481200051756","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"},{"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":"15_CR10"},{"issue":"3","key":"15_CR11","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."},{"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).","key":"15_CR12","DOI":"10.1109\/SCT.1993.336518"},{"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).","key":"15_CR13","DOI":"10.1145\/153850.153905"},{"unstructured":"T. Hirst and D. Harel, \u201cMore about Recursive Structures: Descriptive Complexity and Zero-One Laws\u201d, Proc. 11th Symp. on Logic in Computer Science, New Brunswick, NJ, July, 1996.","key":"15_CR14"},{"key":"15_CR15","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":"15_CR16","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1090\/pspum\/042\/791067","volume-title":"Recursion Theory","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. L., 1985, pp. 323\u2013375."}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63045-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:35:25Z","timestamp":1742600125000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63045-7_15"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540630456","9783540690658"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-63045-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"25 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}