{"entities":{"Q715046":{"pageid":716895,"ns":120,"title":"Item:Q715046","lastrevid":63832239,"modified":"2026-04-11T15:50:55Z","type":"item","id":"Q715046","labels":{"en":{"language":"en","value":"Stochastic game logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6093693"}},"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":"Q715046$2045C061-6668-4876-A933-8758E7F4AEBF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab4f711d5911239d365c21ed260b1efa5055c511","datavalue":{"value":{"text":"Stochastic game logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q715046$AB0A7DD5-AC8F-4EC8-9582-4B41DEFDCE4F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"93f5014487d4fdc3402c5a8e9257fa8bcfbd80be","datavalue":{"value":"1276.68103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$F19CF856-4747-4DC1-BFF3-C09B0F4A5C64","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46e921d835845969ea465c2330db5171d968f1ff","datavalue":{"value":{"entity-type":"item","numeric-id":436314,"id":"Q436314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$077B0C3F-FDBF-4CF3-8411-7CFF25E37560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"90164f212d81b9976368c619f577477b4b6d4fba","datavalue":{"value":{"entity-type":"item","numeric-id":340567,"id":"Q340567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$874D709C-D234-4488-87D0-192EE729E358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0917ecc0ee421e6b16ad9bf93dfa95fb6019942","datavalue":{"value":{"entity-type":"item","numeric-id":715045,"id":"Q715045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$1229B57F-F520-43AB-BC98-4DD72E914745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c3e518c334d462c26c60c459e716d0942607e70d","datavalue":{"value":{"entity-type":"item","numeric-id":235697,"id":"Q235697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$9CEA4FD3-8E32-43F7-9472-A59A88C2A3F0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$9EC94553-F9B8-4DCC-86D5-FCF61EBED74B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"90cd4bb1c8ff7643cee66698544f44be0292260a","datavalue":{"value":{"time":"+2012-10-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q715046$6BBD49D9-164A-4336-8DDA-B3A256A0ACD7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"55b205ca2fe45cdc68439c5664bf8be306617d06","datavalue":{"value":"This paper introduces a temporal logic, referred to as stochastic game logic (SGL), for finite-state probabilistic turn-based multi-player games. The logic is a probabilistic variant of alternating-time temporal logic (ATL) and incorporates elements of probabilistic computation tree logic (PCTL) as well as the possibility to describe path properties by means of deterministic Rabin automata. One of the main novelties of SGL is the ability to bind strategies which allows strategies of nested sub-formulas to depend their decision on the outcome of strategies of outer formulas. This feature makes the model-checking PSPACE-hard, whereas ATL model checking can be solved in polynomial time.  The paper considers the complexity of the model checking problem, i.e., does a given probabilistic multi-player game satisfy a SGL-formula, for different classes of strategies. The main results are that this problem is undecidable for history-dependent strategies, PSPACE-complete for memoryless deterministic strategies, and PSPACE-hard and in EXPSPACE for memoryless randomized strategies. The latter result is obtained by an encoding into the first-order theory of the reals. Finally, the paper shows that the model checking problem for the qualitative fragment of SGL (where bounds are either of the form \\({=}1\\) or \\({>}0\\)) is PSPACE-complete for memoryless strategies.","type":"string"},"datatype":"string"},"type":"statement","id":"Q715046$D6C7FFDB-F52F-48B4-ADA9-E6BF0ACDC0B1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"40003acc9015bc414f0d315cd0e6cdf71202d88a","datavalue":{"value":{"entity-type":"item","numeric-id":236073,"id":"Q236073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$492EB71F-E10B-4C78-B401-411781B98E1B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$9CA49003-0BFD-41DC-8477-FD59021B450C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$5D0391B5-3C01-4AA3-8E37-025BB5C9606C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"410dbaa73c02e2bd5fbd3c00164dc18b5e93e8cc","datavalue":{"value":"91A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$53EAEC50-9AA7-49E8-B54C-2E123FD6FEC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0e3678c4c27859448aaf57c0c464a06d6cc1a175","datavalue":{"value":"03B48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$40FC1589-2D83-4456-A131-5EB6D343A8A6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e96c7029c1a98fb8fd09b95c05b8c5fa462c8432","datavalue":{"value":"6093693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$5705071F-6613-47D9-81E8-F4286B433A21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4adf313dffdd3f1a4d0039134001dfb5403daf8c","datavalue":{"value":"probabilistic multi-player games","type":"string"},"datatype":"string"},"type":"statement","id":"Q715046$7763BF5A-E54E-4695-9C90-43FDD7591499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1ae521718438d9dae164938ac201015537dd61f","datavalue":{"value":"alternating-time temporal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q715046$68DFB037-5F17-41C2-9DE7-F82184915BE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb9f8004d477a3922fe8bde53d670f8b57c48852","datavalue":{"value":"model checking","type":"string"},"datatype":"string"},"type":"statement","id":"Q715046$7C88930A-268C-4AA9-BDE2-DE36435F76D2","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":"Q715046$8A7ED9E8-08DA-432A-B294-2AD01EF4677C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8fbba31ee9e434af395af59ed3c086ba19cc350","datavalue":{"value":"https://doi.org/10.1007/s00236-012-0156-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q715046$412084D0-5707-47B7-A038-885EFE40146A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"57d05fcfa25abd5c7a992630403210609dcc5766","datavalue":{"value":"W2041894791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$8A5C22F9-A6F7-4EB2-B4A2-7665E76D4571","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d969bd9e9070eb4e4b53be99bf5557f5f64d3d3","datavalue":{"value":{"entity-type":"item","numeric-id":3455546,"id":"Q3455546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$1283D37D-7AE7-4D4F-B438-F7E81DA85ED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b52479ce1aed3445cf12b4ee9e791997db4f08cf","datavalue":{"value":{"entity-type":"item","numeric-id":4673428,"id":"Q4673428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$D9E8CC8F-F39B-4857-A623-A9973EBC98AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b0c7436976c5b9893e05c1462fed16a80d7904d","datavalue":{"value":{"entity-type":"item","numeric-id":5322945,"id":"Q5322945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$F63FC98D-4D8E-4651-9940-0B045746D7FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ce71a5e212a8c5cd65d66580e9075eb5aa319ca","datavalue":{"value":{"entity-type":"item","numeric-id":2956706,"id":"Q2956706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$B5D133A9-B461-4FDA-87BB-933AF85BB7B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176492351b6803d6dd45cb238a6cda64a727f5fe","datavalue":{"value":{"entity-type":"item","numeric-id":3519498,"id":"Q3519498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$04C9FF85-9D89-4553-A811-C44543370CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f427c7c6bd6ad411bf67bda5f7112f753e0ab73","datavalue":{"value":{"entity-type":"item","numeric-id":3605522,"id":"Q3605522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$95CE9D1E-D34D-43C6-BE58-DC70A8E26FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa9a404b059d8fda8df0c5b1ed2675d4ad3d104","datavalue":{"value":{"entity-type":"item","numeric-id":5192925,"id":"Q5192925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$62CE69B1-208B-48B8-9B09-C1EE62DA538B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e9740972113806023f4ec7d6f4291a9ddcdd7d1","datavalue":{"value":{"entity-type":"item","numeric-id":979080,"id":"Q979080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$6FB5913B-ED0A-4496-ACD4-903BE99BCBA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e44d75bbb4bb319e62a6775e93e6d1ced1dea813","datavalue":{"value":{"entity-type":"item","numeric-id":5285990,"id":"Q5285990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$E1A20D82-96B1-46E5-AF36-F7B1FE5D706E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$8016A827-3021-4EE7-ABB3-64BC3E0A91A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71ee253892b177799592f03938a61eb6c7732cc","datavalue":{"value":{"entity-type":"item","numeric-id":4369884,"id":"Q4369884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$F51E44B4-70E6-4409-B25E-941E49B80394","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96755a14af5db4e33c8082e7c40e98f6f2d4157e","datavalue":{"value":{"entity-type":"item","numeric-id":2465027,"id":"Q2465027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$7877BE02-BEF0-4734-90D9-C5175CA7272B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a0e856b37ab641259d132d542c40481e9faf36","datavalue":{"value":{"entity-type":"item","numeric-id":1264143,"id":"Q1264143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$161EB922-7862-46EE-B021-C164A81B71EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$65716574-62A0-4E8D-83EF-9E9BEF141329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$B000C99A-06B4-4419-BD18-3734E091225F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e320d5ab20d9378e83c08a862b63bf2725892d4a","datavalue":{"value":{"entity-type":"item","numeric-id":2653567,"id":"Q2653567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$4CE5A926-7087-46EF-BD70-40E23E8F0D5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f1d821bd2a1a38500df8bdaf1b0ad70b8c8ee08","datavalue":{"value":{"entity-type":"item","numeric-id":4385530,"id":"Q4385530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q715046$22FAF0D4-ED5C-4363-A017-0C83EF7611F3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6b553dab5ef24dc2a6655cdae382a7d4738a9c74","datavalue":{"value":"10.1007/S00236-012-0156-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q715046$C4C3BFD0-B48D-4895-B626-2CE8695585F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"724d9c4b9b5db43fbbe5174d96ba360e84e40476","datavalue":{"value":{"entity-type":"item","numeric-id":3525629,"id":"Q3525629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac7b4c5e87fc47ba68bcd9cc6b586a8cf1235430","datavalue":{"value":{"amount":"+0.8026266098022461","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":"Q715046$9F146124-1A2B-41CA-9EC3-AB3CB91CD8DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b7816ddc9c725666c97332f0c2a48e9332fef03","datavalue":{"value":{"entity-type":"item","numeric-id":979080,"id":"Q979080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac7b4c5e87fc47ba68bcd9cc6b586a8cf1235430","datavalue":{"value":{"amount":"+0.8026266098022461","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":"Q715046$C8B75262-146A-4EF3-9123-2C4BEC704B57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"415e88a42b78dc33d2ad21cae3bb2a5da9cab99f","datavalue":{"value":{"entity-type":"item","numeric-id":2946746,"id":"Q2946746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0d49386979ff45d8d82b0760bc51de896705725","datavalue":{"value":{"amount":"+0.8003417253494263","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":"Q715046$53B3569C-6068-4DD8-908D-3FA0262A293A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa61de9746c03f9458e5fbccb5f90dd4b50505df","datavalue":{"value":{"entity-type":"item","numeric-id":516033,"id":"Q516033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e741da3f9f6c02b0a4504b24a4e9e358ba661f95","datavalue":{"value":{"amount":"+0.7990940809249878","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":"Q715046$CD129334-DFBE-40AC-B9E8-38A8D1505209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c340356f3611d4c044f8e96194e7fb4fb69c3efe","datavalue":{"value":{"entity-type":"item","numeric-id":2980973,"id":"Q2980973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3577acbb677e6bf6e2ec1f6d36f70adcfc683001","datavalue":{"value":{"amount":"+0.7882050275802612","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":"Q715046$F0993520-4044-4C26-975A-E18D59C750EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Stochastic game logic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Stochastic_game_logic"}}}}}