{"entities":{"Q537919":{"pageid":539686,"ns":120,"title":"Item:Q537919","lastrevid":62646051,"modified":"2026-04-11T07:29:36Z","type":"item","id":"Q537919","labels":{"en":{"language":"en","value":"Weak MSO with the unbounding quantifier"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5898936"}},"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":"Q537919$C50744FA-2201-4222-96FB-AC3D125AF34D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2dbf631786456b9136aca4f7ec12223d878e4d10","datavalue":{"value":{"text":"Weak MSO with the unbounding quantifier","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q537919$E55E6526-3B8E-491E-B76F-5ACDF833A990","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"90e509dc12051ab18f3f0ecae905a87896754f31","datavalue":{"value":"1227.03051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q537919$242018BF-0E52-4699-B02A-D8015EB170AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f5b3c3247f723a8dd053286a58f85570c0f08c2","datavalue":{"value":{"entity-type":"item","numeric-id":290907,"id":"Q290907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$8EC05585-DBC6-49F8-A656-9030ADDBCF58","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$C349F17E-E6C7-429D-979B-2C881FB67C08","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"987c10c6ecaaa604cff66f7d8ee6e24b6dd4dc1e","datavalue":{"value":{"time":"+2011-05-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q537919$CDA74F1F-D2C2-4889-B97A-7501ECD2526A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3dea66d978408d903e9df8aa59ec6d71d4afa637","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2009/1834/","type":"string"},"datatype":"url"},"type":"statement","id":"Q537919$414B3566-A795-4894-9D7F-82066E6FBA30","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"824447956647be5ea3879efbe635320b011f7d06","datavalue":{"value":"Weak monadic second-order (MSO) logic is the monadic second-order predicate logic over the set \\(\\mathbb N\\) of natural numbers with successor function \\(s(x)=x+1\\) over \\(\\mathbb N\\). Monadic predicates \\(X(x)\\) may be finite or infinite (i.e., may have a finite or infinite set of truth points). But second-order quantification is allowed only over finite predicates. Additionally, there is allowed the unbounding quantifier \\(UX.\\varphi(X)\\) which says that the size of \\(X\\) satisfying \\(\\varphi(X)\\) is unbounded, i.e., \\(UX.\\varphi(X)=\\bigwedge_{n\\in \\mathbb N}\\exists_{\\text{fin}}\\,X\\, (\\varphi(X)\\land |X|\\geq n\\)), where the formula \\(\\varphi(X)\\) does not use the unbounding quantifier.  Fix a set of counters \\(C\\). Define the following operations: 1) \\(c:=c+1\\) (increment counter \\(c\\)); 2) \\(c:=0\\) (reset counter \\(c\\)); 3) \\(c:=\\max(d,e)\\) (store in counter \\(c\\) the maximal value of counters \\(d,e\\)). For a counter valuation \\(v\\in\\mathbb N^C\\) and a finite sequence of counter operations \\(\\pi\\), let \\(v\\pi\\in\\mathbb N^C\\) be the counter valuation obtained from \\(v\\) by applying all the operations in \\(\\pi\\). A max automaton is a finite automaton where each transition is labelled by a finite sequence of counter operations. A \\({run}\\) of the automaton is a sequence of transitions which is consistent with the input word. Fix a run \\(\\rho\\) and let \\(\\pi_{i}\\) be the sequence of counter operations that labels the first \\(i\\) transitions in \\(\\rho\\). For an initial counter valuation \\(v\\in\\mathbb N^C\\) and a counter \\(c \\in C\\), define a sequence \\(\\rho_c\\in \\mathbb N^\\omega\\), \\(\\rho_c=v(c),v\\pi_1(c),v\\pi_2(c),\\dots\\). The acceptance condition of a max automaton is a Boolean combination of conditions: ``the sequence \\(\\rho_c\\) is bounded'', i.e., the acceptance condition is a Boolean combination of conditions lim sup \\(\\rho_{{c}} < \\infty\\).   The main result of the paper is that the classes of \\(\\omega\\)-regular languages represented in weak MSO logic and accepted by deterministic max automata, respectively, coincide.","type":"string"},"datatype":"string"},"type":"statement","id":"Q537919$C3BAD007-26C3-48BF-9C3E-378654E8E206","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q537919$94321D7F-79A2-44CA-B03E-662FA0D4F545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q537919$B9CAD46B-124F-48EE-BE3F-0B00E56EDB3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q537919$B7EAF92D-7C83-4F7F-9FC0-BE5D95E09C0D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64b217e50702cd1fc8b0d541bed93b52002bd4b4","datavalue":{"value":"5898936","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q537919$67E9F9F3-64E3-4313-A65B-C18E4C22815B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q537919$28B9B098-CB68-41AB-BDED-A5E76742F297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78bb99c2168e743a9d42fbd76eb84f4c86b4a6e9","datavalue":{"value":"logical expressibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q537919$D1C0F52B-8711-4B6E-9E29-CA0149A92C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q537919$784C41FB-FFFE-4347-B2ED-0043CC0560B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46181ff269ac4c8f57786f5917ef231e038f3452","datavalue":{"value":"acceptance by automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q537919$C3233DF5-E861-4742-B480-F6B24D8BE5C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c0b65ec3a2203625e099be9b073fc50289e061d","datavalue":{"value":"\\(\\omega\\)-regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q537919$00763023-AD8E-422F-80B5-DD5220DDA880","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":"Q537919$5AC6882D-621E-4407-B9EC-BFC8DB0FAFF2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c83987d951ead3fb164807fb63068489dc8fb3ec","datavalue":{"value":"W2010137316","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q537919$562970FF-FC8B-4FA4-B03C-E7C742E1F0A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f809b829ad226aaf187e107ba4f2f8abde5cfa","datavalue":{"value":{"entity-type":"item","numeric-id":1066675,"id":"Q1066675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$BE809039-9533-437C-85F7-DA65BBB8AD3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39921ea5b5cf71915749d2f66167648a28ef38f4","datavalue":{"value":{"entity-type":"item","numeric-id":5311284,"id":"Q5311284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$6AA5BD27-5834-4F9B-85ED-E7950EA33979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b6a2f3ca3dc684f5ae62aee40fd4ca33c8d8f9b","datavalue":{"value":{"entity-type":"item","numeric-id":2920114,"id":"Q2920114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$FAE6B46A-3AB5-470A-9C24-C9F79ABFDA18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e48ec9bf53dfa196dfd5a60eaf2210746f085a0d","datavalue":{"value":{"entity-type":"item","numeric-id":846364,"id":"Q846364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$1ADA3F5E-DF6A-4B5C-B365-34A32A80FD1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"558a099a89df4ec7022b392b244ac5d890f46244","datavalue":{"value":{"entity-type":"item","numeric-id":3540194,"id":"Q3540194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$E606921E-C470-46C8-B0A8-17396DF0F3A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a358680bf0e6b29ad972a10da07c284c97e546fa","datavalue":{"value":{"entity-type":"item","numeric-id":3519517,"id":"Q3519517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$770AD293-8F3C-4D70-9422-DCA409305938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5fe74d71647df58cbeb87817c49bc896fc5aa69","datavalue":{"value":{"entity-type":"item","numeric-id":2373736,"id":"Q2373736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$BF9E2F89-92F2-4069-A387-BF9F1E7DE648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e771f9d0ae93390472a77d30eacf2cd3712d708","datavalue":{"value":{"entity-type":"item","numeric-id":1118420,"id":"Q1118420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$CFD3520A-9330-42E2-B1D0-520D185A7B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9f773300cd053ea51f6b2e01c0bd0b060f02131","datavalue":{"value":{"entity-type":"item","numeric-id":4323294,"id":"Q4323294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$D5FD1746-114D-4311-95A7-A2568F940069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12c36dad8ed8bedb8c332b46f2630912d3155674","datavalue":{"value":{"entity-type":"item","numeric-id":5313718,"id":"Q5313718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$FB3B8762-BA63-4809-A850-6904C9F5EAFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"385b443e68d2c64d04aed98acb6586cb7ed72e3d","datavalue":{"value":{"entity-type":"item","numeric-id":3288101,"id":"Q3288101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$36193D09-DF67-4647-BFE4-AEF64E5B7645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4fa9df919b27baa2f0a56aeacafb9358c362127","datavalue":{"value":{"entity-type":"item","numeric-id":4088807,"id":"Q4088807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q537919$15FC6899-83EC-4002-9D9D-C73DC0F232A4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"00c3c4a3345dcfcb7c2146c6d565e145c20ee465","datavalue":{"value":"10.1007/S00224-010-9279-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q537919$9753B0CA-9C7B-472E-9B09-D5FBF30C2B1E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db48a8e0589b0458d810546e9a68e738ff70068e","datavalue":{"value":{"entity-type":"item","numeric-id":5389974,"id":"Q5389974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ac43015b0eb29fa495084d29dc49865887595b9","datavalue":{"value":{"amount":"+0.880755603313446","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":"Q537919$82938DCD-43A9-4137-A5FA-16A3D8A44CAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db55fc295b6008f6d096d157bbcbdbeac0ee2758","datavalue":{"value":{"entity-type":"item","numeric-id":2920114,"id":"Q2920114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdb53d740e30170f1ca0a30307ff5a8426ff3fc3","datavalue":{"value":{"amount":"+0.7861694693565369","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":"Q537919$3DB88C9C-865E-48C5-B6EC-CB1A0FDACB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcff3f7f6d72a67c92a1101cfe14cba8713ef939","datavalue":{"value":{"entity-type":"item","numeric-id":5351973,"id":"Q5351973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9523cccc1fc1f9093fdd6a722283d76082a8dbe2","datavalue":{"value":{"amount":"+0.7524265050888062","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":"Q537919$03EAC8FE-4842-45BE-A53A-EC1EEF8D0CC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b94df8375ef40fce88fd997def69bb5bd5b776d","datavalue":{"value":{"entity-type":"item","numeric-id":3586103,"id":"Q3586103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c8d0352991cc3f7ff8305627524b42c65f93b5","datavalue":{"value":{"amount":"+0.751911461353302","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":"Q537919$C43CB95A-1A4F-40FE-84E3-24B33D56D42E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdb02510bd1f2f59529b2f6c03617ed19d355eb7","datavalue":{"value":{"entity-type":"item","numeric-id":2904801,"id":"Q2904801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d3135f044a4a9e00e1c0c8491c817e5a8a0fbdf","datavalue":{"value":{"amount":"+0.7502895593643188","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":"Q537919$A12127E1-6049-45DF-8D13-15F9E7A0D9F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Weak MSO with the unbounding quantifier","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Weak_MSO_with_the_unbounding_quantifier"}}}}}