{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T19:16:01Z","timestamp":1696360561770},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":5032,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2000,6]]},"abstract":"<jats:p>One of the fundamental results of descriptive complexity theory, due to Immerman [13] and Vardi [18], says that a class of ordered finite structures is definable in fixed-point logic if, and only if, it is computable in polynomial time. Much effort has been spent on the problem of <jats:italic>capturing polynomial time<\/jats:italic>, that is, describing all polynomial time computable classes of not necessarily ordered finite structures by a logic in a similar way.<\/jats:p><jats:p>The most obvious shortcoming of fixed-point logic itself on unordered structures is that it cannot count. Immerman [14] responded to this by adding counting constructs to fixed-point logic. Although it has been proved by Cai, F\u00fcrer, and Immerman [1] that the <jats:italic>resulting fixed-point logic with counting<\/jats:italic>, denoted by IFP+C, still does not capture all of polynomial time, it does capture polynomial time on several important classes of structures (on trees, planar graphs, structures of bounded tree-width [15, 9, 10]).<\/jats:p><jats:p>The main motivation for such capturing results is that they may give a better understanding of polynomial time. But of course this requires that the logical side is well understood. We hope that our analysis of IFP+C-formulas will help to clarify the expressive power of IFP+C; in particular, we derive a normal form. Moreover, we obtain a problem complete for IFP+C under first-order reductions.<\/jats:p>","DOI":"10.2307\/2586569","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:04:37Z","timestamp":1146938677000},"page":"777-787","source":"Crossref","is-referenced-by-count":4,"title":["On fixed-point logic with counting"],"prefix":"10.1017","volume":"65","author":[{"given":"J\u00f6rg","family":"Flum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200012196_ref016","first-page":"147","volume":"61","author":"Otto","year":"1996","journal-title":"The expressive power of fixed-point logic with counting"},{"key":"S0022481200012196_ref008","first-page":"517","volume":"60","author":"Grohe","year":"1995","journal-title":"Complete problems for fixed-point logics"},{"key":"S0022481200012196_ref003","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/5.2.213"},{"key":"S0022481200012196_ref004","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1084"},{"key":"S0022481200012196_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"S0022481200012196_ref018","first-page":"137","volume-title":"Proceedings of the 14th ACM symposium on theory of computing","author":"Vardi","year":"1982"},{"key":"S0022481200012196_ref009","first-page":"6","volume-title":"Proceedings of the 13th IEEE symposium on logic in computer science","author":"Grohe","year":"1998"},{"key":"S0022481200012196_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"S0022481200012196_ref002","first-page":"20","volume-title":"Computation theory and logic","author":"Dahlhaus","year":"1987"},{"key":"S0022481200012196_ref005","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1995"},{"key":"S0022481200012196_ref006","first-page":"113","volume-title":"Proceedings of the 6th International Conference on database theory, 1997","author":"Flum"},{"key":"S0022481200012196_ref007","first-page":"231","volume-title":"Computer science logic, 6th workshop, CSL '92, San Miniato 1992, selected papers","author":"Gr\u00e4del","year":"1993"},{"key":"S0022481200012196_ref010","volume-title":"Proceedings of the 7th International Conference on database theory","author":"Grohe","year":"1999"},{"key":"S0022481200012196_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90055-2"},{"key":"S0022481200012196_ref012","volume-title":"Archive for Mathematical Logic","author":"Imhof"},{"key":"S0022481200012196_ref014","first-page":"194","volume-title":"Proceedings of the 2nd IEEE symposium on structure in complexity theory","author":"Immerman","year":"1987"},{"key":"S0022481200012196_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21676-7"},{"key":"S0022481200012196_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200012196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T21:20:53Z","timestamp":1557350453000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200012196\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,6]]}},"alternative-id":["S0022481200012196"],"URL":"https:\/\/doi.org\/10.2307\/2586569","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}