{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:26Z","timestamp":1742617166486,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600848"},{"type":"electronic","value":"9783540494256"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60084-1_92","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:39:08Z","timestamp":1330277948000},"page":"405-416","source":"Crossref","is-referenced-by-count":9,"title":["Graph Connectivity, Monadic NP and built-in relations of moderate degree"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"issue":"1","key":"35_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"M. Ajtai and R. Fagin. Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic, 55(1):113\u2013150, 1990.","journal-title":"Journal of Symbolic Logic"},{"key":"35_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai. \u2306 1 1 formulae on finite structures. Ann. of Pure and Applied Logic, 24:1\u201348, 1983.","journal-title":"Ann. of Pure and Applied Logic"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"S. Cosmadakis. Logical reducibility and monadic NP. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pages 52\u201361, 1993.","DOI":"10.1109\/SFCS.1993.366882"},{"key":"35_CR4","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/malq.19870330107","volume":"33","author":"M. Rougemont de","year":"1987","unstructured":"M. de Rougemont. Second-order and inductive definability on finite structures. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 33:47\u201363, 1987.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"35_CR5","unstructured":"H.-D. Ebbinghaus, J. Flum, and W. Thomas. Einf\u00fchrung in die mathematische Logik. BI, Mannheim, 3rd edition, 1992."},{"key":"35_CR6","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math., 49:129\u2013141, 1961.","journal-title":"Fund. Math."},{"key":"35_CR7","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, pages 43\u201373, 1974."},{"key":"35_CR8","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. Monadic generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 21:89\u201396, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"35_CR9","first-page":"35","volume":"1","author":"R. Fra\u00cfss\u00e9","year":"1954","unstructured":"R. Fra\u00cfss\u00e9. Sur quelques classifications des syst\u00e8mes de relations. Publ. Sci. Univ. Alger. S\u00e9r. A, 1:35\u2013182, 1954.","journal-title":"Publ. Sci. Univ. Alger. S\u00e9r. A"},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"R. Fagin, L. Stockmeyer, and M. Vardi. On monadic NP vs. monadic co-NP. In The Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, pages 19\u201330, 1993.","DOI":"10.1109\/SCT.1993.336544"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"T. Schwentick. Graph connectivity and monadic NP. In Proc. 35th IEEE Symp. on Foundations of Computer Science, pages 614\u2013622, 1994.","DOI":"10.1109\/SFCS.1994.365730"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60084-1_92.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:51:59Z","timestamp":1742597519000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60084-1_92"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600848","9783540494256"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-60084-1_92","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}