{"entities":{"Q2786142":{"pageid":2796880,"ns":120,"title":"Item:Q2786142","lastrevid":83322455,"modified":"2026-05-07T07:13:44Z","type":"item","id":"Q2786142","labels":{"en":{"language":"en","value":"On second-order monadic monoidal and groupoidal quantifiers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5789412"}},"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":"Q2786142$0F9C4654-41DA-4CAD-841B-DC152BE54832","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2e71ef3c2bb43e2a4d5aa2f41cc809ecde477d3","datavalue":{"value":"1214.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$D77395B2-62CB-4042-9143-A5B323246E1F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6b133942b81ab2073ad43afcb7ef0b96f7706dd9","datavalue":{"value":"10.2168/LMCS-6(3:25)2010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$2122BE01-14F6-4581-A9CE-D9A4FEB6EE8C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d6c92a6d1e244ef6727f00b02d0236f9547dd35","datavalue":{"value":{"entity-type":"item","numeric-id":269505,"id":"Q269505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2786142$8793B1E0-B543-491D-8729-3233379170E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ca8a4811cca52a248ccfd30baaf04c265f9ef0a","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2786142$5F6A1D35-B71E-4FE9-9817-C6B7163A96C8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"da58c52dc46c86e7440f2499c9e1bef3537c5562","datavalue":{"value":{"entity-type":"item","numeric-id":2786118,"id":"Q2786118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2786142$23A145DC-A5FD-4F4F-BD2B-973E02866C4D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24079ba03437de62c4e6fda5262431b289580da2","datavalue":{"value":{"time":"+2010-09-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2786142$CF0785AE-F4A3-4A5A-898A-24ACCCB9DB42","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ff994a28cd61b6574961a0eb0bac3dcffdb95e7f","datavalue":{"value":"https://arxiv.org/abs/1009.2893","type":"string"},"datatype":"url"},"type":"statement","id":"Q2786142$326043D4-0028-4699-A170-47D70DA8DCBF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25e5a5f23d3e2e2c05864da16eda493011c33276","datavalue":{"value":"03C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$8ED19EC4-A91A-47FB-9096-7A20C92B3C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$0BED53B5-4C61-4F85-BB7F-C18C7F936396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$3DCF2C3F-927E-41DA-9560-7067281C3BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$99CC71C1-79A9-4E04-B7E8-BA178386C310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$04255053-DB87-4F33-A7CE-A6B43371C4C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$E5616C38-149C-4AAE-B716-FE0D1CCE4439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$446B9692-B81D-43C7-8369-B74BF23F54B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4645fc477327cb10e7e51791a747f01744bebb2f","datavalue":{"value":"5789412","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2786142$70617CDA-F499-4256-A62E-6287EA3CDCC6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2786142$55F27319-20BF-4B86-B2AD-698C1BF09664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01752effe5b7128beb68f689d98deb40dd53dd63","datavalue":{"value":"leaf language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2786142$0B335A8F-C4CB-487F-8D4E-6F0AE12E4046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa92a3c973917f4d18d3a98116d7c819a07a5920","datavalue":{"value":"second-order generalized quantifier","type":"string"},"datatype":"string"},"type":"statement","id":"Q2786142$C61D52DE-480D-43B9-95D3-2BF2782557D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2786142$1023F474-420D-490D-BE53-09B5E687903D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"420132b0a86bb9bedd0eeeab0b7b74055a6e96fb","datavalue":{"value":"descriptive complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2786142$B3064045-0B7F-415C-95F2-07507DD45B9A","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":"Q2786142$D0C5F97C-80AD-4BB3-97F7-DE1EE040E39E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3284d4d46f9b9bd7534574523c6198d26dd8d471","datavalue":{"value":{"text":"On second-order monadic monoidal and groupoidal quantifiers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2786142$33EC130C-CC01-4C83-890C-CBC3787EE865","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a8d9ec1a44afb22ffc7f70d31351c226bba1111","datavalue":{"value":"A groupoid is a finite set \\({G}\\) on which a binary operation \\(\\ast\\) (multiplication) with an identity element \\(e\\) is defined. For a fixed groupoid \\({G}\\), each \\({S}\\subseteq {G}\\) defines a \\({G}\\)-word problem, i.e., a language \\({W(S,G)}\\) composed of all words \\({w}\\), over the alphabet \\({G}\\), that can be bracketed in such a way that \\({w}\\) multiplies out to an element of \\({S}\\). The word problem of a monoid, i.e., an associative groupoid, is defined analogously. Groupoid word problems relate to context-free languages in the same way as monoid word problems relate to regular languages: every such word problem is context-free, and every context-free language is a homomorphic pre-image of a groupoid word problem. NEWLINENEWLINEThe authors study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word problems, equivalently, by regular and context-free languages.NEWLINENEWLINEThey give a computational classification of the expressive power of these logics over strings with varying built-in predicates. In particular, it is shown that ATIME(\\({n}\\)) can be logically characterized in terms of second-order monadic monoidal quantifiers.NEWLINENEWLINETwo open questions are formulated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2786142$89E4C458-D586-41D8-8C61-3FA11369B190","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02bcefaf5c1acfa64adad3bdce00878248fcf63a","datavalue":{"value":{"entity-type":"item","numeric-id":3511462,"id":"Q3511462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5747b4480cfcfbc2a600b566099b74e5b1fce19f","datavalue":{"value":{"amount":"+0.8938931226730347","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":"Q2786142$258EC6F0-12FB-42CA-9037-49CA48C715EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f28a82005f77ed4c66e285be5f4842cfe0f79676","datavalue":{"value":{"entity-type":"item","numeric-id":4637695,"id":"Q4637695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f61d5e7a36c0a2ca4044e52e92b8a502e6939e","datavalue":{"value":{"amount":"+0.7489916682243347","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":"Q2786142$6155688B-3A48-499E-89AD-710787F9713A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15fce0ab40ebbe8d49ac7a46994f7c44c5c080c3","datavalue":{"value":{"entity-type":"item","numeric-id":5271046,"id":"Q5271046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caa8f28b2bb6fd53d258193df8dc958fa0a86624","datavalue":{"value":{"amount":"+0.7384074926376343","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":"Q2786142$DE0C08B4-2A63-4E67-A465-B78CB793FBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6237da8a566c8619c6aad9353ae3d8185e7a1a45","datavalue":{"value":{"entity-type":"item","numeric-id":4453869,"id":"Q4453869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea90dd3e92e9a22aedf70f1b9c3880a873f81e1a","datavalue":{"value":{"amount":"+0.7359982132911682","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":"Q2786142$82C3F44F-B718-4E54-8B2C-89A82A27044A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01b663e42e16167f767820b45f94dd7f5ffb45fa","datavalue":{"value":{"entity-type":"item","numeric-id":5311712,"id":"Q5311712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd81613cd6c95f4d4ba924670ae48bad3763d6de","datavalue":{"value":{"amount":"+0.7355748414993286","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":"Q2786142$5B299042-2579-4DBE-818A-F5098F7D33CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On second-order monadic monoidal and groupoidal quantifiers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_second-order_monadic_monoidal_and_groupoidal_quantifiers"}}}}}