{"entities":{"Q5958134":{"pageid":8134936,"ns":120,"title":"Item:Q5958134","lastrevid":93566276,"modified":"2026-06-05T04:37:10Z","type":"item","id":"Q5958134","labels":{"en":{"language":"en","value":"Dot operators"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715100"}},"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":"Q5958134$D1F1C6E0-542A-4FCD-ACDE-DAA2CD73B8DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"879b73390212967e0b1583ce985aa4d06d26c858","datavalue":{"value":{"text":"Dot operators","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958134$B5E4748C-7DBA-4AC5-A651-0C67D175A174","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3a5ab6e824b710716010feabe73a6d0f6201da40","datavalue":{"value":"0983.68095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958134$A662994B-C3A1-4D66-87B4-C2A8D0F7889D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"13799d025067f0d843ea0389caa18e6e684a5d34","datavalue":{"value":"10.1016/S0304-3975(00)00323-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958134$F0062F1D-6314-47EA-A96A-989574E1389E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5843c7c493d4706c03532f63f307f44c46bc641b","datavalue":{"value":{"entity-type":"item","numeric-id":590547,"id":"Q590547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$DEE9571A-B04A-482A-8564-90131C426589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58acf3741ec940036229b64a01b0d77bd499cb0a","datavalue":{"value":{"entity-type":"item","numeric-id":590536,"id":"Q590536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$2AC81D82-F0E3-4371-979E-40CA3693CB61","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$B758765D-8B52-4CC9-BC00-4BF976485C71","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958134$A526BA77-97B3-421D-B23E-43E79E460F1F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fa4fd0f306202f7cb56e5a89e10c2e90634832aa","datavalue":{"value":"Well-known examples of dot operators are the existential, the counting, and the BP-operator. We generalize this notion of a dot operator so that every language \\(A\\) will determine an operator \\(A\\cdot\\). In fact, we introduce the more general notion of promise dot operators for which the BP-operator is an example. Dot operators are a refinement of the leaf language concept because the class determined by a leaf language \\(A\\) equals \\(A \\cdot P\\). Moreover, we are able to represent not only classes but reducibilities, in fact most of the known polynomial-time reducibilities can be represented by dot operators. We show that two languages determine the same dot operator if and only if they are reducible to each other by polylog-time computable monotone projections.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958134$5280F05B-615E-484B-85F5-9182A47808E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958134$996048A5-D985-49D3-B687-92B2E8144212","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"98421e04ccab6ec8de8e3fac24d5d28c11cb1901","datavalue":{"value":"1715100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958134$302FB9ED-350A-4616-872C-0EF4AEFD8025","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25da6ad1a20589e58c7b421dabcb1590044fbfd9","datavalue":{"value":"dot operators","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958134$D4CAE235-CA1C-4306-93B9-BB47FD05EB21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01752effe5b7128beb68f689d98deb40dd53dd63","datavalue":{"value":"leaf language","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958134$C782ACE4-56D2-4568-9855-41DA1471B99F","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":"Q5958134$DED63BC3-BCD0-437B-A62F-40537F111CEA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dceb582de27df796af18e78f104f60dedd0655a7","datavalue":{"value":{"entity-type":"item","numeric-id":1097029,"id":"Q1097029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$B2745348-DAB1-40D4-9E07-EC3EDD256D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4f9b219f54da4cc88e481211745b7b70548f30","datavalue":{"value":{"entity-type":"item","numeric-id":4039803,"id":"Q4039803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$5225B319-7D54-4395-BC24-248822EDC15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a3f5e6a1ed91a009a4c95875091c741100f2e26","datavalue":{"value":{"entity-type":"item","numeric-id":287160,"id":"Q287160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$0D3D4220-043E-4B57-8159-342B1F91FE3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47b8341f14615b169306046574a7b0720ccb03ee","datavalue":{"value":{"entity-type":"item","numeric-id":1200807,"id":"Q1200807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$E7A00582-4B08-4E68-8A67-46DE3D485484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d5257f71d98a6e1899a8d1ff1a09a30fa28cbba","datavalue":{"value":{"entity-type":"item","numeric-id":3751004,"id":"Q3751004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$05B3E455-E2C5-4CAC-AB9E-3DE02E68288D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7687f6335f1fe70b7baae78354697ab6dcfb8337","datavalue":{"value":{"entity-type":"item","numeric-id":1177170,"id":"Q1177170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$106BC670-BC86-46A9-BFBB-E0F664694F78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd07bc9a9b69ce8a80cf38ac60dbedf570ebf67d","datavalue":{"value":{"entity-type":"item","numeric-id":1109566,"id":"Q1109566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$7AE7035F-2793-49DD-A498-FD4ADDDE35B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81058c196b847ccb46704df00be374ef4587a380","datavalue":{"value":{"entity-type":"item","numeric-id":4007854,"id":"Q4007854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$A0FFEC73-BA24-4F8C-8132-36D907303B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c9f0c22784d06a47744c30712bdd4d14d7c7498","datavalue":{"value":{"entity-type":"item","numeric-id":4887490,"id":"Q4887490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$0DF8E649-5551-4073-8750-96604597B74C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$1790FD32-36B1-43EB-AAED-75C8451746E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02b12708e66d9fc03ea7ba7c93418ff8d5e63879","datavalue":{"value":{"entity-type":"item","numeric-id":1817219,"id":"Q1817219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$A484F22F-B4E1-4689-94B9-181462E6A4F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff365d8186cc4c7ca2a8c01bb1842652c3c232d","datavalue":{"value":{"entity-type":"item","numeric-id":4273947,"id":"Q4273947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$06A15AC1-12FF-4098-A25E-A06564F8E6AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$B1D57A54-0CDA-4BE3-A962-7423AC88AC83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$62401A53-3057-4B86-BBE9-8E2F178CD6BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba0e56df9db89377069ef2057d2ac5bcfceb74c1","datavalue":{"value":{"entity-type":"item","numeric-id":1069296,"id":"Q1069296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$6B1C9719-FA74-47F5-A95B-82ACDD645C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$D093164F-BF53-4E3D-A300-275C31B0BF9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$E45EC95E-8CB1-4E8C-AD5C-31F1421E650B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb2c936121f4f1d6e6f7ab70089a797e73426bb","datavalue":{"value":{"entity-type":"item","numeric-id":3662618,"id":"Q3662618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$2A2B887D-643D-4E3D-8ED7-C61FC168E0D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e73c4b1eb952ce21189627f2e0b84dd36494db","datavalue":{"value":{"entity-type":"item","numeric-id":3771612,"id":"Q3771612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$F5D00AC5-9BAE-4840-80EE-7B98A47D9377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$A18EEC35-C25D-4596-A043-CC3EBE54F173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58caa984504f2a274575f62b4f30ecba0bce4643","datavalue":{"value":{"entity-type":"item","numeric-id":3835025,"id":"Q3835025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$54F01798-0076-4E6B-9451-AFD85B2ABA0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde012ef21d89edd10de7c33ccbb08320345d351","datavalue":{"value":{"entity-type":"item","numeric-id":3990656,"id":"Q3990656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$4D8604EA-423E-4EF3-B117-DB2A58CB7FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a79d7e6ff87438522166be3a4baa3c6ce145a139","datavalue":{"value":{"entity-type":"item","numeric-id":4302854,"id":"Q4302854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$47369816-0B08-4289-9453-F46C6D2B6204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$4214ADF1-5257-48BE-A375-107A15DF8CFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9716957b8f9307cec140776ae6ef1a5565b490b8","datavalue":{"value":{"entity-type":"item","numeric-id":4315092,"id":"Q4315092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$E133F2FC-52EC-483E-B7E3-3BBEDA4ED570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e1c59b20b978e8e0de5a32fdeb6c212dbd6e1a","datavalue":{"value":{"entity-type":"item","numeric-id":1090455,"id":"Q1090455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958134$F7BC0624-E472-45E3-9C9C-4E537697B13F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a32410fbee2dc3ac5dd767e2f9c3647f2b8337cb","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(00)00323-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q5958134$326FF980-A852-48C5-8B0F-4A51AF8165BA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0a34e32d0cb1b4d0d467cfc672b7e4d66a4959a9","datavalue":{"value":"W2914643490","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958134$42120393-5C25-47A8-A448-6EC4D894DD4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b1ba8e7fd129355ed08faffd6498c5c385f5372","datavalue":{"value":{"entity-type":"item","numeric-id":859980,"id":"Q859980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1b3114db6762a7e69259031fd2259f5450cdf4b","datavalue":{"value":{"amount":"+0.7351881265640259","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":"Q5958134$C6A1EDFC-DB61-41DE-907F-6C61F665A1EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b00d2daa2eaf1a6a8815946313492d8919cb564","datavalue":{"value":{"entity-type":"item","numeric-id":5710672,"id":"Q5710672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03f6d288db752e96746fdcc2e3a6f8de325718f1","datavalue":{"value":{"amount":"+0.7316457033157349","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":"Q5958134$CF4C927D-2BD2-4DBD-B8F5-33B8E178A2C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1f4763a233f3948236a57051f99557211b76418","datavalue":{"value":{"entity-type":"item","numeric-id":5711979,"id":"Q5711979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3485da853b9e71206ab2c45d6700799daa13fa67","datavalue":{"value":{"amount":"+0.7189168930053711","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":"Q5958134$47CF0139-7DB0-44FE-A30D-81EE9FBE3AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"384c1a624bead81748678a088d6c174bd13db4ab","datavalue":{"value":{"entity-type":"item","numeric-id":2453555,"id":"Q2453555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e0cbec94ac7a60d85688c5a08dec981d739a70d","datavalue":{"value":{"amount":"+0.718366801738739","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":"Q5958134$6506FA0D-C1D4-45DE-819B-A6919E98F26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2822ebabeab1b33c281876daabd50ca89f20fc1f","datavalue":{"value":{"entity-type":"item","numeric-id":3617079,"id":"Q3617079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47c87ee4e30da968e63254c3071d659ce5ac24b2","datavalue":{"value":{"amount":"+0.7123333811759949","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":"Q5958134$6230292A-6F54-431C-AD23-38D23E0EE696","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dot operators","badges":[]}}}}}