{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:49Z","timestamp":1725663709051},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_177","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:59Z","timestamp":1330262459000},"page":"631-645","source":"Crossref","is-referenced-by-count":1,"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,5,31]]},"reference":[{"key":"51_CR1","first-page":"209","volume-title":"Proc. 23rd ACM Symp. on Theory of Computing","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu, \u201cGeneric Computation and Its Complexity\u201d, Proc. 23rd ACM Symp. on Theory of Computing, pp. 209\u2013219, ACM Press, New York, 1991."},{"issue":"2","key":"51_CR2","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)\n54:2 (1992), 257\u2013290.","journal-title":"J. of Combinatorial Theory (Series B)"},{"key":"51_CR3","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\n41 (1976), 469\u2013480.","journal-title":"J. Sym. Logic"},{"key":"51_CR4","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.\n55 (1976), 385\u2013394.","journal-title":"Proc. Amer. Math. Soc."},{"key":"51_CR5","unstructured":"R. Beigel and W. I. Gasarch, unpublished results, 1986\u20131990."},{"key":"51_CR6","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\n45 (1989), 1\u201338, 227\u2013247.","journal-title":"Ann. Pure and Appl. Logic"},{"key":"51_CR7","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.\n50 (1984), 171\u2013177.","journal-title":"Disc. Math."},{"key":"51_CR8","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.\n21, (1980), 156\u2013178.","journal-title":"J. Comp. Syst. Sci."},{"key":"51_CR9","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":"51_CR10","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."},{"issue":"3","key":"51_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.\n76:3 (1991), 317\u2013336. (Also, Proc. 23rd ACM Symp. on Theory of Computing, New Orleans, pp. 220\u2013229, 1991.)","journal-title":"Israel J. Math."},{"key":"51_CR12","volume-title":"Proc. 8th IEEE Conf. on Structure in Complexity Theory","author":"T. Hirst","year":"1993","unstructured":"T. Hirst and D. Harel, \u201cTaking it to the Limit: On Infinite Variants of NP-Complete Problems\u201d, Proc. 8th IEEE Conf. on Structure in Complexity Theory, IEEE Press, New York, 1993."},{"key":"51_CR13","first-page":"244","volume-title":"12th ACM Symp. on Principles of Database Systems","author":"T. Hirst","year":"1993","unstructured":"T. Hirst and D. Harel, \u201cCompleteness Results for Recursive Data bases\u201d, 12th ACM Symp. on Principles of Database Systems, ACM Press, New York, 1993, 244\u2013252."},{"key":"51_CR14","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":"51_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.\n3 (1972), 615\u2013654.","journal-title":"Proc. London Math. Soc."},{"key":"51_CR16","doi-asserted-by":"crossref","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.","DOI":"10.1090\/pspum\/042\/791067"},{"key":"51_CR17","doi-asserted-by":"crossref","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.\n107 (1993), 145\u2013163.","journal-title":"Theor. Comp. Sci."},{"key":"51_CR18","doi-asserted-by":"crossref","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.\n43, (1991), 425\u2013440.","journal-title":"J. Comp. Syst. Sci."},{"key":"51_CR19","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."}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_177.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:08:06Z","timestamp":1619572086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_177","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}