{"entities":{"Q792083":{"pageid":793931,"ns":120,"title":"Item:Q792083","lastrevid":48696535,"modified":"2026-01-05T15:42:08Z","type":"item","id":"Q792083","labels":{"en":{"language":"en","value":"Propositional dynamic logic of nonregular programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3852427"}},"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":"Q792083$DFCF366A-8EDF-444C-9EB8-6506BDA01D22","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e4ad0c929e88f2ecb77e37f8739c3753efae34b1","datavalue":{"value":{"text":"Propositional dynamic logic of nonregular programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792083$77399A88-3F6C-4FFE-B9E5-207F97AA733F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e0dc35ba43a813fa41b8fe45c536cac51b20eb8e","datavalue":{"value":"0536.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$F68E73E8-A28F-49DD-BBD6-F11AA14CCE6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b6e6fe901dd4ce62a41f323e0142fb831902e3d1","datavalue":{"value":"10.1016/0022-0000(83)90014-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$047D622C-F2B0-4CC6-8E41-9905734D74FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d86d555bd6cd1001c3d6ecad72fc1ab67c5fdce1","datavalue":{"value":{"entity-type":"item","numeric-id":209473,"id":"Q209473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$1EE23203-CEEC-46E2-937B-F88604EF0678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f609d14c1727f970ab5a0ef43992b4a7d4a23fcd","datavalue":{"value":{"entity-type":"item","numeric-id":208770,"id":"Q208770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$A378E0FC-B332-4219-A49B-2ABDFDC81B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"30c66c4f54d3057409e2ea29dce9ea720e46c393","datavalue":{"value":{"entity-type":"item","numeric-id":762059,"id":"Q762059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$20423DF7-CB25-446D-88C4-35B85B7EFA9D","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":"Q792083$3A2A1E3B-57D5-4082-80C1-893C26261E76","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q792083$50EE4A88-541A-47A1-B7FE-ABC67F8276D4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ef541f3f55af81857b37709c628bbd079836e77","datavalue":{"value":"It was shown by \\textit{M. J. Fischer} and \\textit{R. E. Ladner} [J. Comput. Syst. Sci. 18, 194-211 (1979; Zbl 0408.03014)] that the validity problem for regular propositional dynamic logic (PDL) is decidable in deterministic exponential time, and, within a polynomial, this upper bound is the best possible. The authors consider similar problems for context-free PDL, showing that the borderline between decidable and undecidable PDL is extremely close to the original regular PDL, and strikingly that the transition leaps from decidability in exponential time for regular PDL to \\(\\Pi^ 1_ 1\\)-completeness. A comprehensive characterization of the class of programs for which PDL is decidable remains an intriguing topic for future research.","type":"string"},"datatype":"string"},"type":"statement","id":"Q792083$D31EAC51-6D4E-4FDF-822D-F5F2D7C6B041","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$D5AB402C-1C2F-4042-AE08-825103F8B258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$FF55AAFD-583B-4198-B7E3-5380A63F507F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"89a6721807d2106ad3a18783b4fcbc004e6a56c5","datavalue":{"value":"03B60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$5E208B81-1991-46F1-83FD-3C72DF02E1F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$6C698DB7-7910-489D-8B4D-0291CB7680FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$9FAE495C-C408-4C83-84C4-5D559105B159","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9be00d10ec78690636312d4a1aa77b5d24db8bfc","datavalue":{"value":"3852427","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$3E41030D-FC2F-438D-87E3-7A19ACAEF051","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d8f95104569681b12147407e1fc63bde7079389","datavalue":{"value":"context-free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q792083$B890CF2F-A4E3-4930-AE3C-4C2E91CBB8FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5950369e3296ba8752027da07ec6b3ab18326cee","datavalue":{"value":"recursive programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q792083$42C7C35C-6A31-4442-9D4F-4AF2D6881924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a5eef9a7839e51aae1829128fd74061b3797fc5","datavalue":{"value":"propositional dynamic logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q792083$35143528-E05B-4FEC-AF8D-084936744A3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bedf3ba8df14fb0304865561eb75280526591c59","datavalue":{"value":"context-free PDL","type":"string"},"datatype":"string"},"type":"statement","id":"Q792083$7FBBBE10-BF6C-4FBB-A0A6-9B52AF07A9F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q792083$90A3351D-1C24-459B-8466-D80C479F3FA9","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":"Q792083$B4D87614-CC27-4187-97DA-B462BC4648BF","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":"Q792083$D2FE5428-1A64-4625-80CD-FEE5937367FF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a5c1433c3e247c5052f552cba5c0bf513da52ec8","datavalue":{"value":"https://doi.org/10.1016/0022-0000(83)90014-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q792083$A7A9B065-D1E1-49D0-8020-500ECE6C459D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99ff7b25d4e7f98d2542004763c7589aa5dc6387","datavalue":{"value":"W2062879749","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792083$ED731004-1D11-4B4B-B744-E55A0CA64B07","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6952c964346571cc46d55c2182e9c31b3abf5e35","datavalue":{"value":{"entity-type":"item","numeric-id":1236426,"id":"Q1236426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$B35F5885-EE5D-4D52-93E6-7A26EA5177A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83a6823e76c11ef1f853772c882ad2f84a6d8b84","datavalue":{"value":{"entity-type":"item","numeric-id":3292904,"id":"Q3292904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$BC150BA5-609E-470E-B9A5-60643D865AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eeb89c68e650c350803663393d6e0912dfa3f4b2","datavalue":{"value":{"entity-type":"item","numeric-id":4115143,"id":"Q4115143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$DC57F22E-7B72-4642-878F-A243C6578FF0","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":"Q792083$429B46FB-544F-4205-828A-F361ED71A14F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7d9dd414a6b3b2c58f60a1e339698f5282df1d1","datavalue":{"value":{"entity-type":"item","numeric-id":3912024,"id":"Q3912024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$E1A88F32-498C-43AF-BECC-85C0C754EFF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6adad7220c18758e0e6a1fdbbfbac3345ecaf47d","datavalue":{"value":{"entity-type":"item","numeric-id":3953159,"id":"Q3953159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$53C1CFC7-74E4-47AA-B979-F30925E274B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$D130FB8A-7AC1-4E58-871B-84A059347F10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ec7365ae7ff2e7eb7ba57dcda7a377d50b921a5","datavalue":{"value":{"entity-type":"item","numeric-id":1254241,"id":"Q1254241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$4468D6CD-6228-4A42-BB91-83D55BF0EC24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c059d1355bcb0df592c7e924663d48f24f3b387e","datavalue":{"value":{"entity-type":"item","numeric-id":5613949,"id":"Q5613949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$6B7DDE5E-1CFF-4FEC-A80F-315C710C4775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8723c8224d4443bdd7a3d97a7dff5a3dc1827308","datavalue":{"value":{"entity-type":"item","numeric-id":3919070,"id":"Q3919070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$8B70A986-A9CA-4C91-A661-31A2D53CFFD7","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":"Q792083$139474AE-B88D-4DF6-A323-66B7003133BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7d5f7fdd407b024c3b8e20cb24651ffce7db825","datavalue":{"value":{"entity-type":"item","numeric-id":1134756,"id":"Q1134756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$C86FFB81-1590-4390-ABD7-E1694D0679A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$97984122-C92E-40C5-9621-8F0D79E63F87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9f8e374d8379ce975eb6bf78ad8ce5329e04752","datavalue":{"value":{"entity-type":"item","numeric-id":3923621,"id":"Q3923621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792083$652DF87C-0448-4513-9CE4-7880845767F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8a1ddb02559e815c7ce065349e8a1fb76313e45","datavalue":{"value":{"entity-type":"item","numeric-id":801901,"id":"Q801901"},"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":"Q792083$CEE6343D-985C-4B45-96BD-CA1BA2673BD6","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":"b163ab72f2e737a8667b71e3015c47282ec9687a","datavalue":{"value":{"amount":"+0.8790725469589233","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":"Q792083$2797B0C6-8E7E-4947-8A27-33E3173FF59C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e63e136a3f99c164e16dc4b22d6c6e40b53b4bba","datavalue":{"value":{"entity-type":"item","numeric-id":3318101,"id":"Q3318101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb673e425fd522ff94ad25303b7c84a4d7e8806b","datavalue":{"value":{"amount":"+0.8768400549888611","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":"Q792083$278CB7C9-DCF0-40D2-B04E-58E1AA84CC34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4b8bae39ea3582b3d9dbc0059d40b3aef36eeaa","datavalue":{"value":{"entity-type":"item","numeric-id":801682,"id":"Q801682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22677ccdb622cdda4e1cad064012cd7eb6792728","datavalue":{"value":{"amount":"+0.8489197492599487","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":"Q792083$E816AD89-637E-4582-B713-6265DE30562B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"459889d5310106929d088e8b9b294423d01d5621","datavalue":{"value":{"entity-type":"item","numeric-id":2643333,"id":"Q2643333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8ef5fb3f41ec9e579712a36464f00849086b048","datavalue":{"value":{"amount":"+0.8406768441200256","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":"Q792083$C8A69516-A59E-4529-8FB5-B82E1BEA0C7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:792083","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:792083"}}}}}