{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T02:17:33Z","timestamp":1772849853504,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540749141","type":"print"},{"value":"9783540749158","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74915-8_10","type":"book-chapter","created":{"date-parts":[[2007,8,24]],"date-time":"2007-08-24T05:13:35Z","timestamp":1187932415000},"page":"84-98","source":"Crossref","is-referenced-by-count":8,"title":["The Power of Counting Logics on Restricted Classes of Finite Structures"],"prefix":"10.1007","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[]},{"given":"David","family":"Richerby","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-540-73420-8_49","volume-title":"Proc. 34th International Colloquium on Automata, Languages and Programming","author":"A. Atserias","year":"2007","unstructured":"Atserias, A., Bulatov, A., Dawar, A.: Affine systems of equations and counting infinitary logic. In: Proc. 34th International Colloquium on Automata, Languages and Programming. LNCS, vol.\u00a04596, pp. 558\u2013570. Springer, Heidelberg (to appear, 2007)"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/11672142_43","volume-title":"STACS 2006","author":"D. Berwanger","year":"2006","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 524\u2013536. Springer, Heidelberg (2006)"},{"key":"10_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-540-32275-7_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Berwanger","year":"2005","unstructured":"Berwanger, D., Gr\u00e4del, E.: Entanglement: A measure for the complexity of directed graphs with applications to logic and games. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 209\u2013223. Springer, Heidelberg (2005)"},{"issue":"4","key":"10_CR4","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J.-Y. Cai","year":"1992","unstructured":"Cai, J.-Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica\u00a012(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"10_CR5","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B)","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwan, J. (ed.) Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"key":"10_CR6","volume-title":"Proc. 22nd IEEE Annual Symposium on Logic in Computer Science","author":"A. Dawar","year":"2007","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: Proc. 22nd IEEE Annual Symposium on Logic in Computer Science, IEEE Computer Society, Los Alamitos (to appear, 2007)"},{"key":"10_CR7","first-page":"411","volume-title":"Proc. 21st IEEE Annual Symposium on Logic in Computer Science","author":"A. Dawar","year":"2006","unstructured":"Dawar, A., Grohe, M., Kreutzer, S., Schweikardt, N.: Approximation schemes for first-order definable optimisation problems. In: Proc. 21st IEEE Annual Symposium on Logic in Computer Science, pp. 411\u2013420. IEEE Computer Society, Los Alamitos (2006)"},{"key":"10_CR8","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"10_CR9","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica\u00a027, 275\u2013291 (2000)","journal-title":"Algorithmica"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM\u00a048, 1184\u20131206 (2001)","journal-title":"Journal of the ACM"},{"key":"10_CR12","first-page":"6","volume-title":"Proc. 13th IEEE Annual Symposium on Logic in Computer Science","author":"M. Grohe","year":"1998","unstructured":"Grohe, M.: Fixed-point logics on planar graphs. In: Proc. 13th IEEE Annual Symposium on Logic in Computer Science, pp. 6\u201315. IEEE Computer Society, Los Alamitos (1998)"},{"key":"10_CR13","first-page":"63","volume-title":"Proc. 32nd ACM Symposium on Theory of Computing","author":"M. Grohe","year":"2000","unstructured":"Grohe, M.: Isomorphism testing for embeddable graphs through definability. In: Proc. 32nd ACM Symposium on Theory of Computing, pp. 63\u201372. ACM, New York (2000)"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-49257-7_6","volume-title":"Database Theory - ICDT\u201999","author":"M. Grohe","year":"1998","unstructured":"Grohe, M., Mari\u00f1o, J.: Definability and descriptive complexity on databases of bounded tree-width. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 70\u201382. Springer, Heidelberg (1998)"},{"issue":"1","key":"10_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0070","volume":"129","author":"L. Hella","year":"1996","unstructured":"Hella, L.: Logical hierarchies in PTIME. Information and Computation\u00a0129(1), 1\u201319 (1996)","journal-title":"Information and Computation"},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-1-4612-4478-3_5","volume-title":"Complexity Theory Retrospective","author":"N. Immerman","year":"1990","unstructured":"Immerman, N., Lander, E.S.: Describing graphs: A first-order approach to graph canonization. In: Selman, A. (ed.) Complexity Theory Retrospective, pp. 59\u201381. Springer, Heidelberg (1990)"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. Journal of Combinatorial Theory Series B\u00a082, 138\u2013155 (2001)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"10_CR18","series-title":"Electronic Notes in Discrete Mathematics","first-page":"101","volume-title":"International Colloquium on Graph Theory","author":"J. Ne\u0161et\u0159il","year":"2005","unstructured":"Ne\u0161et\u0159il, J., de Ossona Mendez, P.: The grad of a graph and classes with bounded expansion. In: Raspaud, A., Delmas, O. (eds.) International Colloquium on Graph Theory. Electronic Notes in Discrete Mathematics, vol.\u00a022, pp. 101\u2013106. Elsevier, Amsterdam (2005)"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Obdr\u017e\u00e1lek, J.: DAG-width: Connectivity measure for directed graphs. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 814\u2013821 (2006)","DOI":"10.1145\/1109557.1109647"},{"key":"10_CR20","series-title":"Lecture Notes in Logic","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21676-7","volume-title":"Bounded Variable Logics and Counting \u2014 A Study in Finite Models","author":"M. Otto","year":"1997","unstructured":"Otto, M.: Bounded Variable Logics and Counting \u2014 A Study in Finite Models. Lecture Notes in Logic, vol.\u00a09. Springer, Heidelberg (1997)"},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors II: Algorithmic aspects of tree-width. Journal of Algorithms\u00a07(3), 307\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"10_CR22","first-page":"91","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors V: Excluding a planar graph. Journal of Combinatorial Theory Series B\u00a041(1), 91\u2013114 (1986)","journal-title":"Journal of Combinatorial Theory Series B"},{"issue":"2","key":"10_CR23","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XX: Wagner\u2019s conjecture. Journal of Combinatorial Theory Series B\u00a092(2), 325\u2013357 (2004)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P.D. Seymour","year":"1993","unstructured":"Seymour, P.D., Thomas, R.: Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory Series B\u00a058, 22\u201333 (1993)","journal-title":"Journal of Combinatorial Theory Series B"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74915-8_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:45:43Z","timestamp":1619520343000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74915-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540749141","9783540749158"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74915-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}