{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T15:44:49Z","timestamp":1775058289472,"version":"3.50.1"},"reference-count":71,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":5524,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[1998,12]]},"abstract":"<jats:p>Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.<\/jats:p><jats:p>For each <jats:italic>k<\/jats:italic> \u2265 1 we let L<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup> be the fragment of first-order logic consisting of all formulas with at most <jats:italic>k<\/jats:italic> (free or bound) variables. The logics L<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup> are the simplest finite-variable logics. Later, we are going to consider infinitary variants and extensions by so-called counting quantifiers.<\/jats:p><jats:p>Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the L<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>. Around the same time Immerman [45] showed that important complexity classes such as polynomial time (PTIME) or polynomial space (PSPACE) can be characterized as collections of all classes of (ordered) finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth.<\/jats:p>","DOI":"10.2307\/420954","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T03:12:02Z","timestamp":1146971522000},"page":"345-398","source":"Crossref","is-referenced-by-count":26,"title":["Finite Variable Logics in Descriptive Complexity Theory"],"prefix":"10.1017","volume":"4","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600007125_ref026","volume-title":"Theoretical Computer Science","author":"Gr\u00e4del","year":"1998"},{"key":"S1079898600007125_ref013","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/5.2.213"},{"key":"S1079898600007125_ref047","first-page":"194","volume-title":"Proceedings of the 2nd IEEE symposium on structure in complexity theory","author":"Immerman","year":"1987"},{"key":"S1079898600007125_ref051","first-page":"46","volume-title":"Proceedings of the 7th IEEE symposium on logic in computer science","author":"Kolaitis","year":"1992"},{"key":"S1079898600007125_ref042","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00008-0"},{"key":"S1079898600007125_ref040","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0070"},{"key":"S1079898600007125_ref052","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90021-7"},{"key":"S1079898600007125_ref032","first-page":"6","volume-title":"Proceedings of the 13th IEEE symposium on logic in computer science","author":"Grohe","year":"1998"},{"key":"S1079898600007125_ref031","volume-title":"Computer science logic, 11th international workshop CSL '97 (Selected papers)","volume":"1414","author":"Grohe","year":"1998"},{"key":"S1079898600007125_ref044","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"S1079898600007125_ref058","first-page":"345","article-title":"Enumerable sets are diophantic","volume":"11","author":"Matijasevi\u010d","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"S1079898600007125_ref023","unstructured":"Flum J. and Ziegler M. , private communication."},{"key":"S1079898600007125_ref056","first-page":"27","article-title":"The relational model for process control","volume":"4","author":"Livchak","year":"1983","journal-title":"Automated Documentation and Mathematical Linguistics"},{"key":"S1079898600007125_ref015","first-page":"51","volume-title":"Logic colloquium '95","volume":"11","author":"Dawar","year":"1998"},{"key":"S1079898600007125_ref060","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210118"},{"key":"S1079898600007125_ref050","first-page":"191","article-title":"Turing machines that take advice","volume":"28","author":"Karp","year":"1982","journal-title":"L'Enseignement Math\u00e9matique"},{"key":"S1079898600007125_ref041","doi-asserted-by":"publisher","DOI":"10.2307\/421173"},{"key":"S1079898600007125_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60084-1_110"},{"key":"S1079898600007125_ref063","article-title":"The expressive power of fixed-point logic with counting","volume":"61","author":"Otto","year":"1996","journal-title":"Journal"},{"key":"S1079898600007125_ref024","doi-asserted-by":"publisher","DOI":"10.2307\/421196"},{"key":"S1079898600007125_ref002","first-page":"209","volume-title":"Proceedings of the 23rd ACM symposium on theory of computing","author":"Abiteboul","year":"1991"},{"key":"S1079898600007125_ref010","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511803888","volume-title":"Combinatorics: Topics, techniques, algorithms","author":"Cameron","year":"1994"},{"key":"S1079898600007125_ref034","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0099486"},{"key":"S1079898600007125_ref035","first-page":"1","volume-title":"Current trends in theoretical computer science","author":"Gurevich","year":"1988"},{"key":"S1079898600007125_ref054","volume-title":"Proceedings of the 11th IEEE symposium on logic in computer science","author":"Kolaitis","year":"1996"},{"key":"S1079898600007125_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"S1079898600007125_ref028","first-page":"249","volume-title":"Proceedings of the 14th annual symposium on theoretical aspects of computer science","author":"Gr\u00e4del","year":"1997"},{"key":"S1079898600007125_ref033","volume-title":"Proceedings of the 7th international conference on database theory","author":"Grohe","year":"1999"},{"key":"S1079898600007125_ref025","first-page":"231","volume-title":"Computer science logic, 6th workshop, CSL '92, San Miniato 1992, selected papers","volume":"702","author":"Gr\u00e4del","year":"1993"},{"key":"S1079898600007125_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59207-2"},{"key":"S1079898600007125_ref003","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"S1079898600007125_ref062","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1995.523269"},{"key":"S1079898600007125_ref065","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614958"},{"key":"S1079898600007125_ref005","first-page":"5","volume-title":"Studies in model theory","author":"Barwise","year":"1973"},{"key":"S1079898600007125_ref022","first-page":"236","volume-title":"Proceedings of the 12th ACM symposium on theory of computing","author":"Filotti","year":"1980"},{"key":"S1079898600007125_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80027-9"},{"key":"S1079898600007125_ref006","first-page":"292","article-title":"On Moschovakis closure ordinals","volume":"42","author":"Barwise","year":"1977","journal-title":"Journal"},{"key":"S1079898600007125_ref048","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"S1079898600007125_ref071","first-page":"266","volume-title":"Proceedings of the 14th ACM symposium on principles of database systems","author":"Vardi","year":"1995"},{"key":"S1079898600007125_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"S1079898600007125_ref018","first-page":"25","volume-title":"Model-theoretic logics","author":"Ebbinghaus","year":"1985"},{"key":"S1079898600007125_ref064","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21676-7"},{"key":"S1079898600007125_ref059","first-page":"225","volume-title":"Proceedings of the 12th ACM symposium on theory of computing","author":"Miller","year":"1980"},{"key":"S1079898600007125_ref014","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-60178-3_94","volume-title":"Logic and computational complexity: International workshop, LCC '94","volume":"960","author":"Dawar","year":"1995"},{"key":"S1079898600007125_ref046","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"S1079898600007125_ref045","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"S1079898600007125_ref049","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"S1079898600007125_ref055","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90048-7"},{"key":"S1079898600007125_ref029","first-page":"264","volume-title":"Proceedings of the 37th annual IEEE symposium on foundations of computer science","author":"Grohe","year":"1996"},{"key":"S1079898600007125_ref043","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"S1079898600007125_ref061","doi-asserted-by":"publisher","DOI":"10.4064\/fm-82-1-39-83"},{"key":"S1079898600007125_ref019","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1995"},{"key":"S1079898600007125_ref068","first-page":"329","volume-title":"Theory of models","author":"Scott","year":"1965"},{"key":"S1079898600007125_ref027","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614957"},{"key":"S1079898600007125_ref004","first-page":"171","article-title":"Canonical labeling of graphs","author":"Babai","year":"1983","journal-title":"Proceedings of the 15th ACM symposium on theory of computing"},{"key":"S1079898600007125_ref037","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90055-2"},{"key":"S1079898600007125_ref036","first-page":"115","article-title":"From invariants to canonization","volume":"63","author":"Gurevich","year":"1997","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"S1079898600007125_ref012","unstructured":"Dawar A. , Feasible computation through model theory, Ph.D. thesis , University of Pennsylvania, 1993."},{"key":"S1079898600007125_ref067","first-page":"641","article-title":"Deux ou trois choses que je sais de Ln","volume":"47","author":"Poizat","year":"1982","journal-title":"Journal"},{"key":"S1079898600007125_ref069","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1995.523270"},{"key":"S1079898600007125_ref030","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1997.614949"},{"key":"S1079898600007125_ref038","first-page":"549","article-title":"On finite rigid structures","volume":"61","author":"Gurevich","year":"1996","journal-title":"Journal"},{"key":"S1079898600007125_ref057","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19770233608"},{"key":"S1079898600007125_ref017","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1084"},{"key":"S1079898600007125_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"S1079898600007125_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256295"},{"key":"S1079898600007125_ref070","first-page":"137","volume-title":"Proceedings of the 14th ACM symposium on theory of computing","author":"Vardi","year":"1982"},{"key":"S1079898600007125_ref039","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90070-5"},{"key":"S1079898600007125_ref053","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55719-9_96"},{"key":"S1079898600007125_ref066","volume-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"S1079898600007125_ref021","first-page":"43","volume-title":"Complexity of computation","volume":"7","author":"Fagin","year":"1974"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600007125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T15:48:44Z","timestamp":1557503324000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600007125\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,12]]},"references-count":71,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,12]]}},"alternative-id":["S1079898600007125"],"URL":"https:\/\/doi.org\/10.2307\/420954","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,12]]}}}