{"entities":{"Q1111384":{"pageid":1122133,"ns":120,"title":"Item:Q1111384","lastrevid":49223866,"modified":"2026-01-06T19:26:41Z","type":"item","id":"Q1111384","labels":{"en":{"language":"en","value":"On the complexity of deciding fair termination of probabilistic concurrent finite-state programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076622"}},"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":"Q1111384$9F886999-477D-41FC-A4AE-5176FD24F3BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f60b0927d3b445945ead946cc6793fa7631db23","datavalue":{"value":{"text":"On the complexity of deciding fair termination of probabilistic concurrent finite-state programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111384$60D54B8C-99E9-4C63-934E-FFD0E7E02123","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"618745d5f09f13f32af601b1fb6db4361379839a","datavalue":{"value":"0658.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111384$DF07755A-6D38-4303-A911-3A5946F61D66","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d5645c716bf8e51f19f70a1e9721d9b07a75163","datavalue":{"value":"10.1016/0304-3975(88)90031-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111384$C73607C9-5C44-4953-9ABA-92DDBE6DE784","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0fbe9a2f35bfbb97131fdd4f5f88a8af0c602f0","datavalue":{"value":{"entity-type":"item","numeric-id":688713,"id":"Q688713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$6C92074E-FFB0-465D-A0A5-3FC6F85CE52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef70989854b46304c6274e59f7064331acfcdafe","datavalue":{"value":{"entity-type":"item","numeric-id":344509,"id":"Q344509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$128C58DC-205A-48C6-ACFD-A2F987DDF45C","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":"Q1111384$067BAEEA-F855-4E94-AB8B-6251CD75A948","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1111384$03826295-DCDE-4DB2-8E60-204A461A9985","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fda9cc685799da446213dfad006584810cc96fc3","datavalue":{"value":"Systems of probabilistic finite-states concurrent programs are considered and the problem of their fair termination with probability 1 is addressed. Necessary and sufficient conditions for solving this problem under five different fairness assumptions are given.    Moreover, the complexity of the presented problem is analysed and it is proved that, depending on the fairness criterion, it is either complete for PTIME or on the second or third level of the alternating logspace hierarchy.    Finally, lower and upper bounds are given for the same problem in the special case when a more succinct representation of the input is assumed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111384$3B51A6CA-07B5-4A62-B080-CA892FD4571A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111384$0770D958-44DD-45A7-A993-1912668DCE74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111384$28BFB3C5-A4CE-4534-9609-DCF5188A381C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111384$12A05E01-4723-4B1C-9A21-7FC68C1F94C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f2b9e3005a203fdc1ab119829824e08b419c541","datavalue":{"value":"4076622","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111384$224B201E-8FDF-42E7-ACBA-29876277953D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"417a929c7470687a4f36f1646ed55f2f8cb4e7ec","datavalue":{"value":"finite-state programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111384$DCDD2A42-D12F-4553-AB51-E2249685E33A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44664b4b67374cefa5180983b7d744c24ee4f02f","datavalue":{"value":"probabilistic finite-states concurrent programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111384$6CADA7F0-4890-425D-B5FA-89210B8D1844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a277367c3d4e3c3aec102118ab5101d7a653037","datavalue":{"value":"fair termination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111384$9B5AD73E-9FB8-4B66-917D-EB529760670E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"636b794da077dcaa1805ce93cc3d55482029d3dd","datavalue":{"value":"fairness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111384$791F094E-457B-4BDD-8948-82D1FB04EF76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111384$7038F1B0-FC77-4377-8EBC-5B1C3E52C17F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"120593207a84ab2e34c27bd7d3f4ebd1f29a3ef2","datavalue":{"value":{"entity-type":"item","numeric-id":259587,"id":"Q259587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$C9FC1EDA-2B7E-4DDB-9CCA-772B8CB4FAD1","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":"Q1111384$0B19DFDC-D74F-4224-AF36-D19D7CD601CE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecdcae4d9a5ee36e7f138192416054cf8fb75160","datavalue":{"value":{"entity-type":"item","numeric-id":3768395,"id":"Q3768395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$1A13DFAF-9C29-4B16-BBE7-F2B8F6537958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$E11CE8A0-85E6-46F2-B7B6-C49752D7A3FD","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":"Q1111384$355DCEF5-630C-4C10-93E6-E21EAB3FD269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2e80321a5b901dd6bcf10e15a0ea7c4a4a661ba","datavalue":{"value":{"entity-type":"item","numeric-id":4749184,"id":"Q4749184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$67584F96-4020-4F75-A0CE-E22FE51A8E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"355736aab0d2d42ab9391cea6cea55db3559b261","datavalue":{"value":{"entity-type":"item","numeric-id":3316558,"id":"Q3316558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$A402EA19-CBA8-429D-9ED5-09362592B561","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":"Q1111384$1DFA3753-99D0-4528-9090-94306DF92FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8caa6e70c3996e57b90cedc3b297c2f0a135d12","datavalue":{"value":{"entity-type":"item","numeric-id":3217602,"id":"Q3217602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$39C5FFA6-6BE4-4395-9928-94A43543C657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"373c65ef4069b52a23fe230e08a271e32f56a00a","datavalue":{"value":{"entity-type":"item","numeric-id":1235982,"id":"Q1235982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$46EF4C76-D517-4BDD-90AD-6947BB1A30CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd23d993698a0223d91c56a5d6cb2616616568f","datavalue":{"value":{"entity-type":"item","numeric-id":3700836,"id":"Q3700836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$5CC802EF-8063-46AA-B585-816B0BD9CB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"614c6e62be4436a6012854ed27b0876322223f5b","datavalue":{"value":{"entity-type":"item","numeric-id":5528211,"id":"Q5528211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$F28BD3F8-5A5D-464B-85B6-B3537B1C0D37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57375aaeb2518d9af85d4868f1b2eb7c14017efa","datavalue":{"value":{"entity-type":"item","numeric-id":1146980,"id":"Q1146980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$C883020F-074A-44B2-A11A-6048BC951FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3261cf7e2174b332e3482b23b1e1c76c1020c488","datavalue":{"value":{"entity-type":"item","numeric-id":3922147,"id":"Q3922147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$358EC86B-C558-4F33-B379-A8680B11CD6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8f955881ec719424b635d12ed43cbd0176010fe","datavalue":{"value":{"entity-type":"item","numeric-id":1162148,"id":"Q1162148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$59225BE1-C6C5-4E0A-9B22-B5ACEDDA9E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"969b23c15bda365fef0dcb143b85f2f64b2e439b","datavalue":{"value":{"entity-type":"item","numeric-id":1819938,"id":"Q1819938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$EFB549BD-09BF-440E-B044-4C6A8C2F2B88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40f5134eaa4297cc6ad992072c543aec6eb8f762","datavalue":{"value":{"entity-type":"item","numeric-id":4723306,"id":"Q4723306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$86CD156B-9D22-40C3-8A09-0215AF00DA06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8194b210616a81519a29e9c197fab619e01f1c6","datavalue":{"value":{"entity-type":"item","numeric-id":1062759,"id":"Q1062759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$37AF5BFD-C048-4D2F-B3B3-A5CEF54CADC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d693759536f36f5e10c6e72192ac554ac26bf47","datavalue":{"value":{"entity-type":"item","numeric-id":1235979,"id":"Q1235979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$87C1F095-B3B3-4806-8578-C75B9088B52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69cd752232f88c73c259223e4c2d58dd894072f9","datavalue":{"value":{"entity-type":"item","numeric-id":3854629,"id":"Q3854629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111384$6328CC20-864F-4903-9D87-C7539A0DDB7C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"237626805be455ccadb919ac55ab11a2143863ec","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90031-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111384$90CC8608-FBE8-44C4-A0CB-F2FA63F0EED6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e07d9f05bf1b6afe60dd7f974955a7fae7eeb961","datavalue":{"value":"W2077620037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111384$851EDFBC-F62B-4CD4-ACE2-A67CDAEADDA7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af6aef3b01c30597ab09e135da57b73d61c23a15","datavalue":{"value":{"entity-type":"item","numeric-id":3746869,"id":"Q3746869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dce22bb30cda9278a0593f00e8b8a639eeabd5fc","datavalue":{"value":{"amount":"+0.9526975750923156","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":"Q1111384$E227C8A0-83DF-49E4-8D0A-8C127E45EFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0264fd323e8ae4eb2601febca08581f6f64d5e28","datavalue":{"value":{"entity-type":"item","numeric-id":1822937,"id":"Q1822937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"357fa9d18651f2728a211af2bcea5840c20d4008","datavalue":{"value":{"amount":"+0.8851013779640198","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":"Q1111384$ED5E12C7-DA99-4A55-9B4C-A8EA4678E021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe6156f84d05888d2b9a79289d26c67da3a520e6","datavalue":{"value":{"entity-type":"item","numeric-id":3686020,"id":"Q3686020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00e9202d170bb3d61170bda7e236de54c408893c","datavalue":{"value":{"amount":"+0.8431057333946228","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":"Q1111384$2A6847AB-8CBF-4CA3-BD40-CB192664F1B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74402ad885a3f5b5acf63420302fa5876910466d","datavalue":{"value":{"entity-type":"item","numeric-id":3303911,"id":"Q3303911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"511ad1783834ba2c97015d41c871484ebcffe34f","datavalue":{"value":{"amount":"+0.825925886631012","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":"Q1111384$85355070-0F24-4953-814E-01EF225B4849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1cdc966ae2cd044af4720090a26c0347547a1c4","datavalue":{"value":{"entity-type":"item","numeric-id":804304,"id":"Q804304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b45647e4ce97761d326803f16f8c6106329803d8","datavalue":{"value":{"amount":"+0.8206110596656799","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":"Q1111384$3D2A096A-9E57-4827-807A-A88941D1B75C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111384","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111384"}}}}}