{"entities":{"Q4336698":{"pageid":6366298,"ns":120,"title":"Item:Q4336698","lastrevid":108240155,"modified":"2026-11-05T13:44:58Z","type":"item","id":"Q4336698","labels":{"en":{"language":"en","value":"Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1009465"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$8743EA70-B279-4650-BF80-776D41792993","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f99333120bc3b6199b9437f946b62adac99c7e0","datavalue":{"value":{"text":"Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4336698$407A7762-E8AC-468D-BEF1-64F9A27EA1D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7357a6d7ce7cdfdcdbc7425d68fa0a28b544abb8","datavalue":{"value":"0876.03020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$BA3FCD6F-B44F-41A6-9E5A-DB13EA6451D3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f466736e4a4b4501d0136ec6feb8a629013f44a0","datavalue":{"value":{"entity-type":"item","numeric-id":265086,"id":"Q265086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$5F967E96-BB6B-4C15-A507-925893EE85B3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7af1100b7fbaa31e618c4d49342e2fae8da143f3","datavalue":{"value":{"entity-type":"item","numeric-id":2793901,"id":"Q2793901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$CBE363FA-0275-462A-8C6E-80DBE0DA230F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"62c8c7692fa7223a1bc40102133e79e318fde956","datavalue":{"value":{"time":"+1997-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4336698$7DD5CD94-2C74-4AE0-A3A3-E6C10D317043","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$24CE6812-A34C-497C-9DFE-CBD5AB1FC5BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3bc35ecc3144ff65e9737745f556c5739e048b08","datavalue":{"value":"03C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$330BE0E5-ED91-497F-9C17-B324BCBC2BC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$96816129-29B0-4155-8D7C-25F84FDC5550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$3F77E5E1-CB0C-4307-B160-1AAA159AF01E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$6DFFB16D-6219-436A-BA22-241EB6DE7999","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"861b5b625569c448e775306b96d1a0968c4525b9","datavalue":{"value":"1009465","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$B67EAFBA-77DD-42F3-8879-765B7B74FA4F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69e4ea30093d8fa32dfa08d62053fb8ff3268739","datavalue":{"value":"descriptive complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q4336698$53F8A7C0-084F-458F-B828-E0BBAFF90BD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0997899cc0caea6aa52fd9767fd0545ebb374070","datavalue":{"value":"bounded-variable infinitary logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q4336698$7531857A-297D-4E23-A5CB-B667199AF688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb669f092bdb01d5dcfc844ac5c1d03cf9431016","datavalue":{"value":"generalized quantifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q4336698$5EC5B8FD-F4D8-4651-B8C9-CFC6541427ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8c306ac5bbf5cf358785eec041285b1cb8d24de","datavalue":{"value":"zero-one laws","type":"string"},"datatype":"string"},"type":"statement","id":"Q4336698$4EC9B8AD-3F8B-4F2F-B789-8405999B4285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d4d2fd9d3aba13427b19742e855926a12038048","datavalue":{"value":"pebble games","type":"string"},"datatype":"string"},"type":"statement","id":"Q4336698$128D0079-57EB-4B0D-AD87-26153AB693AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fa35c933ce8add28342512e62275ff6630f950f","datavalue":{"value":"Ehrenfeucht-Fraiss\u00e9 games","type":"string"},"datatype":"string"},"type":"statement","id":"Q4336698$3DD5B4AE-8EA3-48EC-8E63-BBCB6F5B3FAF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$BA6ADAA4-7A49-4957-B829-F5F79181CCF5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b71f4eebbbb6cbc24ad300e74a6a182289086a1","datavalue":{"value":"https://doi.org/10.1002/malq.19970430203","type":"string"},"datatype":"url"},"type":"statement","id":"Q4336698$C4541916-A17E-4DA9-9956-DF796E61D1D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"105a5fe2a6e60bee4d230c1a538c95ba635b836c","datavalue":{"value":"W2065195009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$346A490E-7B3F-4701-9062-5ED944122179","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9ec5cfdad88195e1e2d0fdfc43308ee09ae4c50","datavalue":{"value":{"entity-type":"item","numeric-id":4281518,"id":"Q4281518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$81DBA30C-9416-40EC-AAF0-DADDF4793FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$2384C939-3A80-4997-9B8C-3F26D6A8CC68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98625ed8a97eb6d2931df92b273a7f7a72b6d12c","datavalue":{"value":{"entity-type":"item","numeric-id":4202939,"id":"Q4202939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$DFAB7162-C97E-4E3A-BEE7-4E40DF1FB215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ffac9d9bb94cc497aeb5076809d90cc9cce0a3","datavalue":{"value":{"entity-type":"item","numeric-id":4525286,"id":"Q4525286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4336698$0FA92E32-3DA1-4C8C-A04E-313F7B26FD22","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e196fe4c2fe3736f2b4f898cf9d886853a7c2b3","datavalue":{"value":"10.1002/MALQ.19970430203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4336698$6B4F73D4-29AF-44E1-BB95-E2C4360543CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ff1bc9545f4c25f7fbbbea90458d24b511068e4","datavalue":{"value":{"entity-type":"item","numeric-id":1363784,"id":"Q1363784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11eb6aff7e6bd48ed0a83096f07768b7fcdab16c","datavalue":{"value":{"amount":"+0.8037293553352356","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4336698$A01DF21E-57C0-4720-A32C-C74BE262EE32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02733fc9f7ab3dc41911f39d9fc0968fb57c1dbf","datavalue":{"value":{"entity-type":"item","numeric-id":3747760,"id":"Q3747760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c21f87bc6c9e33f1bbec77a81e336959f41aae25","datavalue":{"value":{"amount":"+0.8036487698554993","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4336698$FABD2445-9BCD-4FEF-8C5A-E185CF834527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e9cc7ef8fd8d30e2743101b1761bb92158c7984","datavalue":{"value":{"entity-type":"item","numeric-id":1193591,"id":"Q1193591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"159c5048cd339fa1ee7d2fd056092204b85da20f","datavalue":{"value":{"amount":"+0.7890833020210266","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4336698$2B563F5A-48A8-4AB0-9784-B5823EB41F8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"145e16102924489d49fb4c46ee8eede861d58952","datavalue":{"value":{"entity-type":"item","numeric-id":920075,"id":"Q920075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0fa3b5e0104385250db89b1a87c536de842c6e6","datavalue":{"value":{"amount":"+0.7856512665748596","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4336698$45915DCC-9D3D-460F-93DC-782209641DEB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e7b75d28871bb4051e004f076b2e94704ede0536","datavalue":{"value":"With an identification of finite models and binary strings, a logic \\(\\mathcal L\\) captures a complexity class \\(\\mathcal C\\) iff every language in \\(\\mathcal C\\) is the class of finite models of some sentence over \\(\\mathcal L\\) and, conversely, every such model class is in \\(\\mathcal C\\) (for background see \\textit{H.-D. Ebbinghaus} and \\textit{J. Flum}, Finite Model Theory (1995; Zbl 0841.03014)). Logics which have a zero-one law cannot capture complexity classes arising from reasonable models of computation. More precisely, for every sentence over such a logic the fraction of all models of size \\(n\\) which satisfy the sentence goes either to \\(0\\) or to \\(1\\) as \\(n\\) goes to infinity and consequently the logic for example lacks the ability to express that a model has even cardinality. An example for a logic which has a zero-one law is the logic \\({\\mathcal L}^{\\omega}_{\\infty\\omega}\\), which is obtained by closing first order logic under infinite conjunctions and disjunctions while requiring that each single formula contains at most finitely many variables. Logics such as least and partial fixed point logic, as well as transitive closure logic can be viewed as fragments of \\({\\mathcal L}^{\\omega}_{\\infty\\omega}\\). As a consequence these logics inherit the property of having a zero-one law and will not capture complexity classes. However these logics capture some well-known complexity classes if restricted to finite models with an additional successor relation, see the article for corresponding references. The article considers logics which capture some complexity class if restricted to finite models with an additional successor relation, which do not capture a complexity class w.r.t. all finite models due to having a zero-one law, but which are not a fragment of \\({\\mathcal L}^{\\omega}_{\\infty\\omega}\\). \\textit{A. Dawar} [In: D. Leivant (ed.), Logic and Computational Complexity, Lect. Notes Comput. Sci. 960, 393-413 (1995)]\\ and \\textit{A. Dawar} and \\textit{E. Gr\u00e4del} [Proc. 10th IEEE Ann. Symp. on Logic in Computer Science 1995, 54-64 (1995)] show that a logic \\({\\mathcal L}_1\\) with these properties can be obtained by adding to first order logic a uniform sequence of generalized quantifiers 3COL which corresponds to the graph property of being colorable with 3 colors. Here an application of the generalized quantifier 3COL to a formula \\(\\varphi\\) with two \\(k\\)-tuples of free variables, for some \\(k\\), yields a new formula which has the intended meaning that the graph with vertex set equal to the set of \\(k\\)-tuples over the universe and edge relation as given by \\(\\varphi\\) can be colored with 3 colors. The author considers a logic \\({\\mathcal L}_2\\) which is obtained similarly by augmenting first order logic with a uniform sequence of generalized quantifiers CUB which corresponds to the graph property of having a cubic subgraph. He argues that, like \\({\\mathcal L}_1\\), the logic \\({\\mathcal L}_2\\) captures the class of sets computable in logarithmic space with the additional help of an \\(\\mathcal NP\\) oracle, and that \\({\\mathcal L}_2\\) has a zero-one law, but is not a fragment of \\({\\mathcal L}^{\\omega}_{\\infty\\omega}\\). The author raises the question whether the logics \\({\\mathcal L}_1\\) and \\({\\mathcal L}_2\\) have the same expressive power. In this connection he shows that on the one hand there are problems which are definable in both logics, but not in first order logic, that is, both logics have a non-trivial intersection, while on the other hand the two underlying \\(\\mathcal NP\\)-complete problems are not equivalent w.r.t. first-order translations, that is, one of the standard methods for showing the equivalence of logics does not apply.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4336698$23854BF8-7BBC-4C88-ACB2-76E758675CB5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Logics_with_Zero-One_Laws_that_Are_Not_Fragments_of_Bounded-Variable_Infinitary_Logic"}}}}}