{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:31:28Z","timestamp":1762101088084},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642162411"},{"type":"electronic","value":"9783642162428"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16242-8_32","type":"book-chapter","created":{"date-parts":[[2010,10,4]],"date-time":"2010-10-04T12:51:59Z","timestamp":1286196719000},"page":"447-458","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Model Expansion"],"prefix":"10.1007","author":[{"given":"Antonina","family":"Kolokolova","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongmei","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eugenia","family":"Ternovska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"32_CR1","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/A:1004275029985","volume":"49","author":"H. Andr\u00e9ka","year":"1998","unstructured":"Andr\u00e9ka, H., van Benthem, J., N\u00e9meti, I.: Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic\u00a049(3), 217\u2013274 (1998)","journal-title":"Journal of Philosophical Logic"},{"issue":"3","key":"32_CR2","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.M. Barrington","year":"1990","unstructured":"Barrington, D.M., Immerman, N., Straubing, H.: On uniformity within NC\n                1. Journal of Computer and System Sciences\u00a041(3), 274\u2013306 (1990)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"32_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A.: A hierarchy for nondeterministic time complexity. Journal of Computer and System Sciences\u00a07(4), 343\u2013353 (1973)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"32_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1342991.1342998","volume":"9","author":"M. Denecker","year":"2008","unstructured":"Denecker, M., Ternovska, E.: A logic of non-monotone inductive definitions. ACM transactions on computational logic (TOCL)\u00a09(2), 1\u201352 (2008)","journal-title":"ACM transactions on computational logic (TOCL)"},{"key":"32_CR5","volume-title":"Finite model theory","author":"H.D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite model theory. Springer, Heidelberg (1995)"},{"key":"32_CR6","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Complexity of computation, SIAM-AMC, vol.\u00a07, pp. 43\u201373 (1974)"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. In: Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2001), pp. 195\u2013206 (2001)","DOI":"10.1145\/375551.375579"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E.: Capturing Complexity Classes by Fragments of Second Order Logic. Theoretical Computer Science\u00a0101, 35\u201357 (1992)","journal-title":"Theoretical Computer Science"},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.2307\/2586808","volume":"64","author":"E. Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E.: On the restraining power of guards. Journal of Symbolic Logic\u00a064, 1719\u20131742 (1999)","journal-title":"Journal of Symbolic Logic"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/421196","volume":"3","author":"E. Gr\u00e4del","year":"1997","unstructured":"Gr\u00e4del, E., Kolaitis, P.G., Vardi, M.Y.: On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic\u00a03, 53\u201369 (1997)","journal-title":"Bulletin of Symbolic Logic"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0304-3975(98)00308-9","volume":"224","author":"E. Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E., Otto, M.: On logics with two variables. Theoretical Computer Science\u00a0224, 73\u2013113 (1999)","journal-title":"Theoretical Computer Science"},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Walukiewicz, I.: Guarded fixed point logic. In: Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1999), pp. 45\u201355 (1999)","DOI":"10.1109\/LICS.1999.782585"},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Relational queries computable in polytime. In: Fourteenth Annual ACM Symposium on Theory of Computing (STOC 1982), pp. 147\u2013152 (1982)","DOI":"10.1145\/800070.802187"},{"key":"32_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive complexity. Springer, New York (1999)"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"69","author":"M. Jurdzinski","year":"1998","unstructured":"Jurdzinski, M.: Deciding the winner in parity games is in UP \u2229 co-UP. Information Processing Letters\u00a069, 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"32_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004)"},{"key":"32_CR17","unstructured":"Liu, Y., Levesque, H.J.: A tractability result for reasoning with incomplete first-order knowledge bases. In: 18th Int. Joint Conf. on Artif. Intell. (IJCAI 2003), pp. 83\u201388 (2003)"},{"key":"32_CR18","unstructured":"Livchak, A.: Languages for polynomial-time queries. In: Computer-based modeling and optimization of heat-power and electrochemical objects, p. 41 (1982)"},{"key":"32_CR19","unstructured":"Mitchell, D., Ternovska, E.: A framework for representing and solving NP search problems. In: 20th National Conf. on Artif. Intell. (AAAI), pp. 430\u2013435 (2005)"},{"key":"32_CR20","unstructured":"Patterson, M., Liu, Y., Ternovska, E., Gupta, A.: Grounding for model expansion in k-guarded formulas with inductive definitions. In: 22nd International Joint Conference on Artificial Intelligence, IJCAI 2007 (2007)"},{"key":"32_CR21","unstructured":"Stockmeyer, L.: The Complexity of Decision Problems in Automata Theory. Ph.D. thesis, MIT (1974)"},{"key":"32_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/978-3-642-16242-8_43","volume-title":"LPAR-17","author":"S. Tasharrofi","year":"2010","unstructured":"Tasharrofi, S., Ternovska, E.: Capturing NP for search problems with built-in arithmetic. In: Ferm\u00fcller, C., Voronkov, A. (eds.) LPAR-17. LNCS, vol.\u00a06397, pp. 610\u2013624. Springer, Heidelberg (2010)"},{"key":"32_CR23","unstructured":"Ternovska, E., Mitchell, D.: Declarative programming of search problems with built-in arithmetic. In: 21st International Joint Conference on Artificial Intelligence, IJCAI 2009 (2009)"},{"key":"32_CR24","unstructured":"Trahtenbrot, B.: The impossibility of an algorithm for the decision problem for finite domains. Doklady Academii Nauk SSSR\u00a070, 569\u2013572 (1950) (in Russian)"},{"key":"32_CR25","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: Fourteenth Annual ACM Symposium on Theory of Computing (STOC 1982), pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: On the complexity of bounded-variable queries. In: Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 1995), pp. 266\u2013276 (1995)","DOI":"10.1145\/212433.212474"}],"container-title":["Lecture Notes in Computer Science","Logic for Programming, Artificial Intelligence, and Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16242-8_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T13:25:01Z","timestamp":1553174701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16242-8_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642162411","9783642162428"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16242-8_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}