{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:40:06Z","timestamp":1737063606338,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425540"},{"type":"electronic","value":"9783540448020"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44802-0_7","type":"book-chapter","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T04:15:38Z","timestamp":1180671338000},"page":"84-98","source":"Crossref","is-referenced-by-count":0,"title":["Capture Complexity by Partition"],"prefix":"10.1007","author":[{"given":"Yijia","family":"Chen","sequence":"first","affiliation":[]},{"given":"Enshao","family":"Shen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,30]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1093\/logcom\/5.2.213","volume":"5","author":"A. Dawar","year":"1995","unstructured":"A. Dawar. Generalized quantifiers and logical reducibilities. Journal of Logic and Computation, 5(1995), 213\u2013226.","journal-title":"Journal of Logic and Computation"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"A. Dawar and E. Gr\u00e4del. Generalized quantifiers and 0-1 laws. in Proceedings of 10th IEEE Symposium on Logic in Computer Science, 54\u201364, 1995.","DOI":"10.1109\/LICS.1995.523244"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum, Finite Model Theory. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"7_CR4","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, 43\u201373, 1974."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"G. Fayolle, S. Grumbach, and C. Tollu. Asymptotic probabilities of languages with generalized quantifiers, in Proceedings of 8th IEEE Symposium on Logic in Computer Science, 199\u2013207, 1993.","DOI":"10.1109\/LICS.1993.287587"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"E. Gr\u00e4del. Capturing complexity classes by fragments of second-order logic. Theoretical Computer Science, 101(1992), 35\u201357.","journal-title":"Theoretical Computer Science"},{"key":"7_CR7","unstructured":"E. Gr\u00e4del, et al. Problems in finite model theory. Available at: http:\/\/www.mgi.informatik.rwth-aachen.de\/FMT\/ , June 2000."},{"key":"7_CR8","unstructured":"H. Imhof. Logiken mit Partitionsquantoren. Diplomarbeit, Freiburg University, 1992."},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16(1987), 760\u2013778.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(1988), 935\u2013938.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Graduate Texts in Computer Science, Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"issue":"1\u20132","key":"7_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(97)00086-8","volume":"184","author":"T. Lacoste","year":"1997","unstructured":"T. Lacoste. 0-1 laws by preservation. Theoretical Computer Science, 184(1\u20132):237\u2013245, 30, 1997.","journal-title":"Theoretical Computer Science"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.2307\/2273679","volume":"48","author":"J. Malitz","year":"1984","unstructured":"J. Malitz. Downward transfer of satisfiability for sentences of L 1,1. Journal Symbolic Logic, 48(1984), 1146\u20131150.","journal-title":"Journal Symbolic Logic"},{"key":"7_CR14","first-page":"1271","volume":"38","author":"E. Shen","year":"1993","unstructured":"E. Shen. Partition logics and transitive closure logics (Abstract). Bulletin of Science (Chinese), 38(1993), 1271\u20131272.","journal-title":"Bulletin of Science"},{"issue":"6","key":"7_CR15","first-page":"540","volume":"24","author":"E. Shen","year":"1996","unstructured":"E. Shen. Partition logics and colored pebble games. Prog. Maths. (Chinese), 24(6) (1996), 540\u2013546.","journal-title":"Prog. Maths."},{"issue":"4","key":"7_CR16","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1002\/1521-3870(200010)46:4<477::AID-MALQ477>3.0.CO;2-R","volume":"46","author":"E. Shen","year":"2000","unstructured":"E. Shen and Y. Chen. The downward transfer of elementary satisfiability of partition logics. Mathematical Logic Quarterly, 46, 477\u2013487, No. 4, 2000.","journal-title":"Mathematical Logic Quarterly"},{"key":"7_CR17","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0304-3975(95)00113-1","volume":"166","author":"E. Shen","year":"1996","unstructured":"E. Shen and Q. Tian. Monadic partition logics and finite automata. Theoretical Computer Science, 166(1996), 63\u201381.","journal-title":"Theoretical Computer Science"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0022-0000(92)90043-I","volume":"45","author":"I. A. Stewart","year":"1992","unstructured":"I. A. Stewart. Using the Hamiltonian path operator to capture NP. Journal of Computer and System Sciences, 45, 127\u2013151 (1992).","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44802-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:02:30Z","timestamp":1737061350000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44802-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425540","9783540448020"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44802-0_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}