{"entities":{"Q924718":{"pageid":926566,"ns":120,"title":"Item:Q924718","lastrevid":77822009,"modified":"2026-05-06T10:08:02Z","type":"item","id":"Q924718","labels":{"en":{"language":"en","value":"Reachability in recursive Markov decision processes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5276410"}},"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":"Q924718$DE6579C3-F752-4B8C-8097-15A5AE356C16","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4e53c2b3a45f0fd4ab96e5dec63a025f24a19844","datavalue":{"value":{"text":"Reachability in recursive Markov decision processes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q924718$DA788560-70E9-482C-90A1-8A0EE3877B6A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a4ed5344ac97a89bb18c5917666ae154c09803f8","datavalue":{"value":"1145.91011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q924718$793FC3F1-148E-4ABB-B062-F0DA9F3B26F1","rank":"normal"}],"P16":[{"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":"Q924718$1F534983-FB94-47A9-A086-894BEBB0EB7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e225f798ff5e7614b09b8c51599bcf33fc63cabe","datavalue":{"value":{"entity-type":"item","numeric-id":391113,"id":"Q391113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$C5DECC60-4774-4C55-B4D3-D05D92577BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97d285282e4a9951aa1b8c348642148d118ee6e0","datavalue":{"value":{"entity-type":"item","numeric-id":278753,"id":"Q278753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$0BA89AAD-D2F4-4698-9A96-0656895DAB44","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":"Q924718$C440BE30-E15E-4B26-A2C2-14704AEAC2D2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$9DAB5687-F686-4FF4-ABA8-C570B4AC852A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f7bef1c16279678ad54ff2c564f5522370b3cfa2","datavalue":{"value":{"time":"+2008-05-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q924718$309A30B4-8B73-4BD7-8E77-59EC70FBA591","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"067cd395fbe8f556b0a79d1ed2caa98d9b32050d","datavalue":{"value":"A class of infinite-state Markov decision processes generated by stateless pushdown automata is considered. This class corresponds to 1 1/2-player games over graphs generated by BPA systems or (equivalently) 1-exit recursive state machines. An extended reachability objective is specified by two sets \\(S\\) and \\(T\\) of safe and terminal stack configurations, where the membership to \\(S\\) and \\(T\\) depends just on the top-of-the-stack symbol. The question is whether there is a suitable strategy such that the probability of hitting a terminal configuration by a path leading only through safe configurations is equal to (or different from) a given \\(x\\) in \\((0,1)\\). It is shown that the qualitative extended reachability problem is decidable in polynomial time, and that the set of all configurations for which there is a winning strategy is effectively regular. More precisely, this set can be represented by a deterministic finite-state automaton with a fixed number of control states. This result is a generalization of a recent theorem by Etessami and Yannakakis which says that the qualitative termination for 1-exit RMDPs (which exactly correspond to our 1 1/2-player BPA games) is decidable in polynomial time. Interestingly, the properties of winning strategies for the extended reachability objectives are quite different from the ones for termination, and new observations are needed to obtain the result. As an application, the EXPTIME-completeness of the model-checking problem is obtained for 1 1/2-player BPA games and qualitative PCTL formulae.","type":"string"},"datatype":"string"},"type":"statement","id":"Q924718$3567E1D6-F0B9-4272-9048-9EFB4609041E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c82436212510eb3fd57a05c9debac7e41dff5f00","datavalue":{"value":{"entity-type":"item","numeric-id":226578,"id":"Q226578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$2B48FE92-D34E-4B2C-82CB-844F5C6346A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8f34675a74b150d19473221b06b085ebc8156162","datavalue":{"value":"91A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q924718$B5C04F87-B70D-4BA7-A6CE-32DCD415B7BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q924718$9594B9D7-51EB-42E7-8CD9-EE77BDD17681","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3a6d5ca41dce7ad5af68c015081e1740afacd023","datavalue":{"value":"5276410","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q924718$DB2D7DAF-BDFF-429F-ADCA-E5FA0AA51320","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbd1f99995fb6a13da62a377ba6327166316e976","datavalue":{"value":"Markov decision processes","type":"string"},"datatype":"string"},"type":"statement","id":"Q924718$07BB2AF9-9436-4991-B7EA-AAFEC275BD67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5358f4ff9b33bdcf646917348056fc0539b7c8ec","datavalue":{"value":"Temporal logics","type":"string"},"datatype":"string"},"type":"statement","id":"Q924718$FB3F2A1E-9164-40F8-89E1-4124D4959D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f0b5189bba2dd49e57311a3938178cf41735940","datavalue":{"value":"Stochastic games","type":"string"},"datatype":"string"},"type":"statement","id":"Q924718$0C9A3D86-03EF-4DF0-B65A-8379AC8FC630","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"531a52a4ab12ab6e2b5be84834036762ed677445","datavalue":{"value":{"entity-type":"item","numeric-id":13928,"id":"Q13928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$FF5E17CF-089C-4ED7-A8CC-F3AE232D05DC","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":"Q924718$BD332767-0280-4915-B016-16B41EDC9216","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"12fac3e1ddca47ff7ce106c297a49fabbed7bb6d","datavalue":{"value":"https://doi.org/10.1016/j.ic.2007.09.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q924718$116D3199-DE66-426A-B1D9-168CAE772A12","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"25ff92adbe6b8788b0575ec2652214d7cd522c3c","datavalue":{"value":"W2101561362","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q924718$2B7B3768-730E-499E-BE79-558FB370DE08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"58166d2dec15bb9c4046220833826b2bdaa6563e","datavalue":{"value":{"entity-type":"item","numeric-id":5137353,"id":"Q5137353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$1193FE5B-01C7-4C25-B665-82129F73034C","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":"Q924718$35911697-F76F-4116-ADD7-ECBCB75D4827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e7a108370169c16838733bc613c6abdf38f709","datavalue":{"value":{"entity-type":"item","numeric-id":6044114,"id":"Q6044114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$25468DE8-5AF8-4599-81FA-A66033CCA8F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d65cc8f2e5ea23c3bd01560d132b8a831f35fc62","datavalue":{"value":{"entity-type":"item","numeric-id":5710670,"id":"Q5710670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$5E29C946-2750-444D-848E-0C07640797B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e902457964a312a605389238232d33897eb4c84c","datavalue":{"value":{"entity-type":"item","numeric-id":1887158,"id":"Q1887158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$15A65B93-C16A-4DC3-A861-A06048650AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6caf9c4f5f4d778c04cb9948f99bacdf8f1fc5bb","datavalue":{"value":{"entity-type":"item","numeric-id":5716837,"id":"Q5716837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$8767FAA1-5375-48B6-9464-5471BFDD4F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8245407078fa850810d9cb7e91abe1e153facccb","datavalue":{"value":{"entity-type":"item","numeric-id":5449837,"id":"Q5449837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$FA577764-17F0-4BB7-87A0-7CCAD8C99F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6fe751a07a354b5b4176618fc695ef7344724d5","datavalue":{"value":{"entity-type":"item","numeric-id":5954951,"id":"Q5954951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$2D4BE8BA-5F77-4FEC-BA28-2A16C1BC2956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9539532d16bcb82516fae2db58a1eb7e9c6ca7b","datavalue":{"value":{"entity-type":"item","numeric-id":5538132,"id":"Q5538132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$5BAA05BF-F97E-45B3-A371-B5848D90DF18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e53d9e53c3c574e8c7675f6ec5036e8ca0ad199b","datavalue":{"value":{"entity-type":"item","numeric-id":1343864,"id":"Q1343864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$BF90262C-16C8-44E9-85C8-49F117ADB7A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"278018e2bacb6d8ea592fa12a67c371e077b2897","datavalue":{"value":{"entity-type":"item","numeric-id":1229833,"id":"Q1229833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$172A46E0-F655-4AA2-909A-7814FB2F944F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a032d33673d5ba9c1e698848960782495104c1b","datavalue":{"value":{"entity-type":"item","numeric-id":1854405,"id":"Q1854405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q924718$95DF5A8E-B81F-4FC6-A19F-D1584A6F8A2F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9b4d27751b2ac05b546a44f39a2f0b78d7830a3a","datavalue":{"value":"10.1016/J.IC.2007.09.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q924718$14B792CA-CCE6-4A34-ACE2-F12E2DB9F53B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95b3073c1696d5786906b7f56b0ff38b9cca77c9","datavalue":{"value":{"entity-type":"item","numeric-id":5756595,"id":"Q5756595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cd23eff8d243fee299446b8d0d65fe56c0fb4d3","datavalue":{"value":{"amount":"+0.9988579154014589","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":"Q924718$658A0D1A-8256-4BA5-89FB-CA63611225DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a1ec6580f066f34334a6a3c7cb1e76eb195d99d","datavalue":{"value":{"entity-type":"item","numeric-id":2796398,"id":"Q2796398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05d0171bfd1b354a9ed1a5e9085d7c65bc20d92c","datavalue":{"value":{"amount":"+0.8528385758399963","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":"Q924718$1010AC7C-6277-4002-95B0-4DC0D497512B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66bacba585d51ccac48955f8a0b480b51110cf61","datavalue":{"value":{"entity-type":"item","numeric-id":5716837,"id":"Q5716837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c86d57ba7de416c9f9645db3340637d93326ed9","datavalue":{"value":{"amount":"+0.8527714610099792","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":"Q924718$B120F742-B916-484A-9C06-C2F3A8F5E161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5054cd88ae19e97978a2828c27953f9c7d3d095","datavalue":{"value":{"entity-type":"item","numeric-id":719240,"id":"Q719240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7be0d490998f38aa23927dd44e9f83d21862b913","datavalue":{"value":{"amount":"+0.8505801558494568","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":"Q924718$E1461EE7-472C-4503-8BAE-0B89255C908C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01025a3ef2aa38f3d153d5060bf43b5e7cd4a0b7","datavalue":{"value":{"entity-type":"item","numeric-id":5389978,"id":"Q5389978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6807fec08b53948573fdf776317d39cea3202a13","datavalue":{"value":{"amount":"+0.8443121910095215","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":"Q924718$391C8D8F-0911-4BB1-B9D7-1EB9530CCB52","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reachability in recursive Markov decision processes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Reachability_in_recursive_Markov_decision_processes"}}}}}