{"entities":{"Q801901":{"pageid":803749,"ns":120,"title":"Item:Q801901","lastrevid":48761641,"modified":"2026-01-05T19:35:36Z","type":"item","id":"Q801901","labels":{"en":{"language":"en","value":"Undecidability of PDL with \\(L=\\{a^{2^ i}| i\\geq 0\\}\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3880675"}},"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":"Q801901$85038BCD-5027-4BE6-99D2-EDD212563FDA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a90e579b97758cc9223c19bbd9523b66396a437b","datavalue":{"value":{"text":"Undecidability of PDL with \\(L=\\{a^{2^ i}| i\\geq 0\\}\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q801901$1D340B86-CF58-4405-B381-2678E4F8CE0D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cbc3f6274d1002bd0084e17d89d013c5122fae7b","datavalue":{"value":"0553.03029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$C5B52340-75E3-4F8E-BB65-58475387EE67","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f1dd4e353305a2d25e3dd81d05d4f7fab35735de","datavalue":{"value":"10.1016/0022-0000(84)90005-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$7FABE3E6-031C-4437-9CB0-CF0B1658A100","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c5832f8876614de1887b6fff71a1066143db327e","datavalue":{"value":{"entity-type":"item","numeric-id":786129,"id":"Q786129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$5BC04DCB-D2EF-4CFE-B595-403D336B94CF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$0C6A3F38-66C1-4C76-B746-618FFF063DCF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q801901$34523160-5879-4CCD-8663-87012DCAAA3A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e80cecaa72c43fe8c0bd67c091243c4a7310e02","datavalue":{"value":"The validity problem of regular PDL (Propositional Dynamic Logic) was shown to be decidable in deterministic exponential time by \\textit{M. J. Fischer} and \\textit{R. E. Ladner} [J. Comput. Syst. Sci. 18, 194-211 (1979; Zbl 0408.03014)]. The same problem can become \\(\\Pi^ 1_ 1\\)-complete with the addition of a bit of context-free programs. Indeed, \\textit{D. Harel, A. Pnueli} and \\textit{J. Stavi} [J. Comput. Syst. Sci. 26, 222-243 (1983; Zbl 0536.68041)] have given some simple classes of such a bad behavior. This paper gives another nonregular PDL of a very bad kind, showing that the validity problem for PDL with the addition of \\(L=\\{a^{2^ i}| i\\geq 0\\}\\) is \\(\\Pi^ 1_ 1\\)-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q801901$D21E439B-96AA-46AC-85C0-E7F56C7AFB1F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$1DD30041-E21C-48FC-A921-189BAE1F0270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$C5C1DD89-F596-4543-9B22-8B34935B5E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$7F72AC65-EF72-4C88-B7A1-629916656C90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$EC7E100C-BC79-4FCB-A969-A165B837D6FE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d58ff3725f7b7e10eff05ee56bb65529a05e634","datavalue":{"value":"3880675","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$4E89C84C-C6DF-4A37-9666-D1B725F5353A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c96c670cb5bb3f93d571a5f56f1e88c84388368c","datavalue":{"value":"validity problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q801901$E66E96B5-B241-4A78-AB33-41FD12A915FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6721114f39173577694cf24a1b46849a7225c33","datavalue":{"value":"Propositional Dynamic Logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q801901$D22D8323-C15A-4614-86BA-376B8F274CE3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"50a4d88aaef452ee91d36bc895e7495d5ed6f713","datavalue":{"value":{"entity-type":"item","numeric-id":195143,"id":"Q195143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$13904E23-17E7-41DA-AA60-CE7C593E11C3","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":"Q801901$4CDCF56D-3F98-41DB-ACCC-563DCAA065E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e24c1eda0dd94fa1dc984ca77ef87a5ff67b7c56","datavalue":{"value":"https://doi.org/10.1016/0022-0000(84)90005-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q801901$6AD4E420-5094-43A6-95C0-8A38BB24F1BA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"607cc47d3ff869269db02638c6f6cacf9e4f990a","datavalue":{"value":"W2031775313","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801901$6DBB67D3-6CAC-438A-A23A-B3A7B0F15C3B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3e0bf6d66ae7c4b6b46e88d6d5b96072d8e8fa","datavalue":{"value":{"entity-type":"item","numeric-id":5597521,"id":"Q5597521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$CEDAFE87-6BBA-4F66-B121-59F2ABD3FC2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47c57a1bc98a9d819c8c4b25347f0c45d96256b1","datavalue":{"value":{"entity-type":"item","numeric-id":1258296,"id":"Q1258296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$53558ADD-BE6F-414B-8931-8AC21DA1CFB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbf1ba170fae28e63e92407b948b3875ee6ea399","datavalue":{"value":{"entity-type":"item","numeric-id":3313253,"id":"Q3313253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$98923FD1-295E-42D6-9549-EEEE95497E77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a49bedc120937d2ca2c0da20fbb588f395782764","datavalue":{"value":{"entity-type":"item","numeric-id":3318101,"id":"Q3318101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$2C0E9A82-A73F-49D3-AB2A-BED6135CBB6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e51636baa00b00ee9af6bbcde64f417bff981286","datavalue":{"value":{"entity-type":"item","numeric-id":792083,"id":"Q792083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$6BD89934-13A0-469A-A5A5-E79B1EE64FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e12ce99e75f00697efa1f5f9afd862b773370cf1","datavalue":{"value":{"entity-type":"item","numeric-id":1147690,"id":"Q1147690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$0633DAF2-69F9-4C82-A884-F1E9EDB497F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8375e11ce45f9ec75069670248a6039513460faf","datavalue":{"value":{"entity-type":"item","numeric-id":2540183,"id":"Q2540183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$1DBF78A1-2DB0-4163-AEC6-1E7AF11453FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d213b1af57f6f45a5d764214e8263b3bd8012e13","datavalue":{"value":{"entity-type":"item","numeric-id":5509685,"id":"Q5509685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$9EE2A6D7-95F0-4029-95BB-BE046DD12976","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f37c9255332d22e7b15af86fb9a96ef9cff53122","datavalue":{"value":{"entity-type":"item","numeric-id":3330494,"id":"Q3330494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801901$3AB95CBC-AF2A-48C2-8A30-1129215E8D50","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8c64005798fa47d1e2e9fd7c57841c444121a30","datavalue":{"value":{"entity-type":"item","numeric-id":792083,"id":"Q792083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4274e2d6ed51b7a849f780a726fca19c7e1fdd60","datavalue":{"value":{"amount":"+0.9022696614265442","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":"Q801901$D0999F02-5A77-4215-8CD2-F7757AD723A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89d28c16903d87b354df9973c509ef865711c16c","datavalue":{"value":{"entity-type":"item","numeric-id":3137712,"id":"Q3137712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"938636ecde30c1141a71f7d9495968aff5143cca","datavalue":{"value":{"amount":"+0.8465046286582947","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":"Q801901$60CAC448-6AA3-4527-81D8-14A94E3D62BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5161e70e2a34646dd831d3da7f66fa24716b2321","datavalue":{"value":{"entity-type":"item","numeric-id":1065545,"id":"Q1065545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c16849fed261e933be00ea64072e2819776cde13","datavalue":{"value":{"amount":"+0.8404075503349304","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":"Q801901$75428399-8AA9-4F98-9C9D-45910FF0B69F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"768482f8f9714678cf33eb17d53f669594342a5a","datavalue":{"value":{"entity-type":"item","numeric-id":1923105,"id":"Q1923105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51225ba30ef56613dd8322e0cc00f0c886da2180","datavalue":{"value":{"amount":"+0.8363339304924011","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":"Q801901$D548309C-FA1E-4FCA-9870-63215495B523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88fe49233b127130c388971a5621d42a322af9c6","datavalue":{"value":{"entity-type":"item","numeric-id":3330494,"id":"Q3330494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13b16bf8e81e17f70218d538b973bb46e4097299","datavalue":{"value":{"amount":"+0.8352125883102417","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":"Q801901$759429B8-815D-4345-988C-EE012200DE30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:801901","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:801901"}}}}}