{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T22:10:26Z","timestamp":1737065426387,"version":"3.33.0"},"reference-count":38,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show that the (NP\u2010complete) problem CUB, being the problem of deciding whether a graph has a cubic subgraph, can not be defined in<jats:italic>L<\/jats:italic><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-stack-1.gif\" xlink:title=\"urn:x-wiley:09425616:media:MALQ19970430203:tex2gif-stack-1\"\/>and so the logic (\u00b1CUB)*[FO] has a zero\u2010one law and can not be regarded as a fragment of<jats:italic>L<\/jats:italic><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-stack-2.gif\" xlink:title=\"urn:x-wiley:09425616:media:MALQ19970430203:tex2gif-stack-2\"\/>. It had previously been shown that the logic (\u00b13COL)*[FO], where 3COL is the problem of deciding whether a graph can be 3\u2010coloured, enjoys a similar status. In an attempt to clarify their relative expressibilities, we show that the problems 3COL and CUB are not equivalent with respect to first\u2010order translations but that there exist problems definable in (\u00b13COL)*[FO] and (\u00b1CUB)*[FO] that are not first\u2010order definable: it remains open as to whether these two logics have the same expressibility. In order to prove our results we slightly extend a technique due to Cai, F\u00fcrer and Immerman, and we formulate and play (extended Ehrenfeucht\u2010Fra\u00efss\u00e9) games very similar to those proposed by Kolaitis and V\u00e4\u00e4n\u00e4nen, and Gr\u00e4del.<\/jats:p>","DOI":"10.1002\/malq.19970430203","type":"journal-article","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T20:56:26Z","timestamp":1180817786000},"page":"158-178","source":"Crossref","is-referenced-by-count":2,"title":["Logics with Zero\u2010One Laws that Are Not Fragments of Bounded\u2010Variable Infinitary Logic"],"prefix":"10.1002","volume":"43","author":[{"given":"Iain A.","family":"Stewart","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Afrati F. S. S.Cosmadakis andM.Yannakakis On Datalog vs. polynomial time. In: Proc. 10th ACM Symp. Principles of Database Systems 1991 pp.13\u201325.","key":"e_1_2_1_2_2","DOI":"10.1145\/113413.113415"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_2","DOI":"10.1007\/3-540-56503-5_19"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_2","DOI":"10.1016\/0022-0000(90)90022-D"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_2","DOI":"10.2307\/2272133"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_2","DOI":"10.1007\/BF01305232"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_2","DOI":"10.1007\/3-540-13331-3_51"},{"unstructured":"Dawar A. Feasible Computation through Model Theory. PhD Thesis University of Pennsylvania1993.","key":"e_1_2_1_8_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_2","DOI":"10.1007\/3-540-60178-3_94"},{"doi-asserted-by":"crossref","unstructured":"Dawar A. andE.Gr\u00e4del Generalized quantifiers and 0\u20101 laws. Proc. 10th IEEE Ann. Symp. on Logic in Computer Science1995 54\u201364.","key":"e_1_2_1_10_2","DOI":"10.1109\/LICS.1995.523244"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_2","DOI":"10.4064\/fm-49-2-129-141"},{"key":"e_1_2_1_12_2","series-title":"SIAM\u2010AMS Proceedings 7","first-page":"43","volume-title":"Complexity of Computation","author":"Fagin R.","year":"1974"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_2","DOI":"10.1016\/0304-3975(93)90218-I"},{"key":"e_1_2_1_14_2","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8ms de relations","volume":"1","author":"Fra\u00efss\u00e9 R.","year":"1954","journal-title":"Publ. Sci. Univ. Alger."},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","year":"1979","author":"Carey M. R.","key":"e_1_2_1_15_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_2","DOI":"10.1007\/BFb0023764"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_2","DOI":"10.1016\/0304-3975(92)90149-A"},{"key":"e_1_2_1_18_2","first-page":"1","volume-title":"Trends in Theoretical Computer Science","author":"Gurevich Y.","year":"1988"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_2","DOI":"10.1016\/0022-0000(82)90011-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_2","DOI":"10.1016\/S0019-9958(86)80029-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_2","DOI":"10.1137\/0216051"},{"doi-asserted-by":"crossref","unstructured":"Immerman N. Expressibility as a complexity measure: Results and directions. In: Proc. 2nd IEEE Ann. Symp. on Structure in Complexity Theory1987 pp.194\u2013202.","key":"e_1_2_1_22_2","DOI":"10.1109\/PSCT.1987.10319271"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_2","DOI":"10.1137\/0217058"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_2","DOI":"10.1090\/psapm\/038\/1020810"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_2","DOI":"10.1007\/978-1-4612-4478-3_5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_2","DOI":"10.1016\/0890-5401(92)90021-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_2","DOI":"10.1016\/0168-0072(94)00025-X"},{"volume-title":"Model theory and computer science: An appetizer. Handbook of Logic in Computer Science","year":"1992","author":"Makowsky J. A.","key":"e_1_2_1_28_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_2","DOI":"10.1007\/BFb0049333"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_2","DOI":"10.1016\/S0022-0000(73)80031-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_2","DOI":"10.1093\/logcom\/1.6.861"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_2","DOI":"10.1016\/0022-0000(92)90043-I"},{"key":"e_1_2_1_33_2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.3233\/FI-1993-18106","article-title":"Logical characterizations of bounded query classes II: Polynomial\u2010time oracle machines","volume":"18","author":"Stewart I. A.","year":"1993","journal-title":"Fund. Informat."},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_2","DOI":"10.1007\/BF01195200"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_2","DOI":"10.1093\/logcom\/4.4.337"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_2","DOI":"10.1016\/0304-3975(94)00175-I"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_2","DOI":"10.1002\/malq.19970430102"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_2","DOI":"10.1016\/0304-3975(76)90061-X"},{"doi-asserted-by":"crossref","unstructured":"Vardi M. Y. The complexity of relational query languages. In: Proc. 14th ACM Ann. Symp. on Theory of Computing1982 pp.137\u2013146.","key":"e_1_2_1_39_2","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.19970430203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:44:42Z","timestamp":1737063882000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430203"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430203","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}