{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T10:43:46Z","timestamp":1749725026466},"reference-count":32,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":4334,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1995,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present game\u2010theoretic characterizations of the complexity\/expressibility measures \u201cdimension\u201d and \u201cthe number of variables\u201d as Least Fixed Point queries. As an example, we use these characterizations to compute the dimension and number of variables of Connectivity and Connectivity.<\/jats:p>","DOI":"10.1002\/malq.19950410110","type":"journal-article","created":{"date-parts":[[2007,6,3]],"date-time":"2007-06-03T01:16:43Z","timestamp":1180833403000},"page":"111-134","source":"Crossref","is-referenced-by-count":1,"title":["Dimension Versus Number of Variables, and Connectivity, too"],"prefix":"10.1002","volume":"41","author":[{"given":"Gregory L.","family":"McColm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70722-5"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274958"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.2307\/2272133"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0082721"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"e_1_2_1_7_2","volume-title":"Computational Models of Games","author":"Condon A.","year":"1989"},{"key":"e_1_2_1_8_2","unstructured":"Dewar A. S.Lindell andS.Weinstein Infinitary Logic and Inductive Definability over Finite Structures. Univ. Penn. Tech. Report IRCS 92\u201320 (1992)."},{"key":"e_1_2_1_9_2","first-page":"7","volume-title":"Complexity of Computations","author":"Fagin R.","year":"1974"},{"key":"e_1_2_1_10_2","unstructured":"Gr\u00e4del E. andG.McColm On the Power of Deterministic Transitive Closure. Information and Computation To appear in Information and Computation."},{"key":"e_1_2_1_11_2","unstructured":"Gr\u00e4del E. andG.McColm Hierarchies in transitive closure logic stratified Datalog and infinitary logic. Proceedings 33rd Annual IEEE Symposium on Foundations of Computer Science FOCS'92."},{"key":"e_1_2_1_12_2","unstructured":"Grohe M. Bounded arity hierarchies in fixed point logics. Ph.D. Thesis University of Frieburg1993."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80045-5"},{"key":"e_1_2_1_14_2","first-page":"65","article-title":"Number of quantifiers is better than number of tape cells","volume":"25","author":"Immerman N.","year":"1981","journal-title":"J. Comp. System Sci."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90059-B"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"Kolaitis P. andM.Vardi On the expressive power of Datalog: Tools and a case study. 9th ACM SIGACT\u2010SIGART\u2010SIGMOD Symposium: Principles of Database Systems (1990) pp.61\u201371.","DOI":"10.1145\/298514.298542"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90021-7"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(77)90443-0"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"Lakshmanan V. andA.Mendelzon Inductive pebble games and the expressive power of datalog. Proceedings 8th ACM SIGACT\u2010SIGART\u2010SIGMOD Symosium: Principles of Database Systems1989 pp.301\u2013310.","DOI":"10.1145\/73721.73751"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90043-2"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093636105"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90053-5"},{"key":"e_1_2_1_25_2","unstructured":"McColm G. Pebble games and the fine structure of least fixed point logic. Submitted."},{"key":"e_1_2_1_26_2","unstructured":"McColm G. The dimension of the negation of transitive closure. To appear in J. Symbolic Logic."},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.2307\/2038552"},{"key":"e_1_2_1_28_2","volume-title":"Elementary Induction on Abstract Structures","author":"Moschovakis Y.","year":"1974"},{"key":"e_1_2_1_29_2","volume-title":"Descriptive Set Theory","author":"Moschovakis Y.","year":"1979"},{"key":"e_1_2_1_30_2","first-page":"289","volume-title":"Computation and Proof Theory","author":"Moschovakis Y.","year":"1983"},{"key":"e_1_2_1_31_2","unstructured":"Moschovakis Y. Unpublished manuscript."},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19870330107"},{"key":"e_1_2_1_33_2","doi-asserted-by":"crossref","unstructured":"Vardi M. Complexity of relational query languages. 14th ACM Symposium on Theory of Computing1982 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19950410110","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19950410110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T17:57:50Z","timestamp":1698256670000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19950410110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,1]]}},"alternative-id":["10.1002\/malq.19950410110"],"URL":"https:\/\/doi.org\/10.1002\/malq.19950410110","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,1]]}}}