{"entities":{"Q1119628":{"pageid":1130377,"ns":120,"title":"Item:Q1119628","lastrevid":66168903,"modified":"2026-04-12T08:00:22Z","type":"item","id":"Q1119628","labels":{"en":{"language":"en","value":"An arithmetical hierarchy in propositional dynamic logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4097353"}},"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":"Q1119628$8C3E3420-7B42-4A07-A8F0-F1F8D60D410D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"46f80a6373a959ef3a9f79fd91a1fbe1a893eb23","datavalue":{"value":{"text":"An arithmetical hierarchy in propositional dynamic logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1119628$76465F6C-0F5B-468F-AD7D-9F4A95A66695","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6fbfd87ef9111971a53fc3b5f16e429bc43f5a0f","datavalue":{"value":"0671.03022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119628$1121D01D-0226-4228-A015-7B4E6BD6C538","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7cbc70227cfaf2bec7578f14dd5e6a509783bba3","datavalue":{"value":"10.1016/0890-5401(89)90033-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119628$70CF1EFC-9038-4CC4-B9DD-C8EE7594CE0C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee82e28c61d82ea4afc6397d787c08c710206e4d","datavalue":{"value":{"entity-type":"item","numeric-id":786542,"id":"Q786542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119628$D9BFEF3C-2387-4B5A-90AF-6F993881574F","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":"Q1119628$EF9A896B-FD21-461D-9D88-6E232E7799EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1119628$03D49885-86BB-4DA9-A686-82D1AA20B752","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8310e55fc2c549fd05b65ecc8412de034b17430c","datavalue":{"value":"Let \\(\\Sigma_ n^{PDL}\\) and \\(\\Pi_ n^{PDL}\\) denote the classes of formulas of propositional dynamic logic of the form \\(<a_ 1>[a_ 2]<a_ 3>...\\{a_ n\\}p\\) and \\([a_ 1]<a_ 2>[a_ 3]...\\{a_ n\\}p\\), respectively, where \\(a_ i\\) are modality-free programs, p is a modality- free formula and \\(\\{a_ n\\}\\) denotes \\([a_ n]\\) or \\(<a_ n>\\) depending on parity of n. It is shown that in some models \\(\\Sigma_ n^{PDL}\\) and \\(\\Pi_ n^{PDL}\\)-formulas define exactly the \\(\\Sigma^ 0_ n\\) and \\(\\Pi^ 0_ n\\)-sets of the Kleene-Mostowski hierarchy. It follows that alternation of modalities defines a strict hierarchy of PDL-formulas relative to their expressive power. Another corollary is the Berman- Paterson theorem: PDL with tests is strongly more expressive than PDL without tests. There are some inaccuracies in the proof but they are easily improvable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$D187E623-3E23-4967-BA62-DC8DE913B489","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119628$FE1557D7-484C-4094-85A3-CC3F05E92568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8e3f40e3cc87753c4e0b7d7ce4bdc00805f626f","datavalue":{"value":"68N01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119628$3C46A3E9-95C5-4F15-807E-C5EAEC407CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119628$34D28BDB-1913-4CB0-B260-75DA32EE82FB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e149b23ef6cbe66b877f95156388056aa95d264","datavalue":{"value":"4097353","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119628$A7C5929B-7CFF-4969-ABE5-0832772577F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d3317fee091a183b95c82d29dc1e995b7455f26","datavalue":{"value":"arithmetical hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$DEB1E591-3C97-4613-BA57-813A8DA32E80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a5eef9a7839e51aae1829128fd74061b3797fc5","datavalue":{"value":"propositional dynamic logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$50A445CA-2538-484E-8AE6-8A0427146363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c87ad845aef2d0cd1924d6040f18b2d424b0bd2b","datavalue":{"value":"Kleene-Mostowski hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$14B0543A-A6DD-4E13-98C9-8232B50ECD76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64986fd413ad64b8170d98ee53e4dc531fdc0176","datavalue":{"value":"alternation of modalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$87357FDC-5FB4-4AAD-979F-9A7CFA4C36FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e16fdb519452f3bafdb17bd5ad06b8194f047110","datavalue":{"value":"expressive power","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$85201A76-11E4-4A74-89C2-73A87DD2F272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50c6cea109955e6d6618ea75e8123878e53c3d54","datavalue":{"value":"Berman-Paterson theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$9AF19676-493B-4D38-AFAA-306FDA2B1B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9006e65c5888ecb8fa3584bde44b35773c529a6","datavalue":{"value":"tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119628$BC252D95-2E58-476C-8BD5-582EF17CB53B","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":"Q1119628$B818346B-C3B2-42A2-8620-3F6EBEB141AF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"501af759e464f6dc3f34b07f4d3eda868048ec6a","datavalue":{"value":"https://doi.org/10.1016/0890-5401(89)90033-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1119628$0DA9740D-0B4B-4E5E-B337-410E1380F0DE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d677192767987c1b0c583af1048e1125decf2dd6","datavalue":{"value":"W2041330005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119628$7263208A-5A97-4B52-B3E7-E6136F09A72C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d1e5663ae3b79b8c83988a81f4ef678ce31f23f","datavalue":{"value":{"entity-type":"item","numeric-id":1156482,"id":"Q1156482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119628$516CFB7C-A5E5-47BC-851B-6D96A3502C3F","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":"Q1119628$2177FBF9-7C6E-42DA-A2A0-14AA072F40F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0e3a179147832b2b1c96869b8d44ccac54dac91","datavalue":{"value":{"entity-type":"item","numeric-id":4343990,"id":"Q4343990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119628$DFD6BD77-9F3F-4FE0-ABEE-F77C3130C8B8","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":"Q1119628$372FE318-75B0-49CE-AB0E-4458E532DA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56aa7a343db226e6c7da9bd7db585a412df58862","datavalue":{"value":{"entity-type":"item","numeric-id":5678435,"id":"Q5678435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119628$2695BF18-25C6-4FF6-88F0-612589A0AE28","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67c6d13aa064c7837313912929ff517e42f36f45","datavalue":{"value":{"entity-type":"item","numeric-id":3337454,"id":"Q3337454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80b99df6107fb5eefbb498285be715f99aa02714","datavalue":{"value":{"amount":"+0.92634434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$E0789198-8FBC-4D45-A032-EB58D1F8BB4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd9ce39678e56391f03664eabf2b9fc8a8c004f8","datavalue":{"value":{"entity-type":"item","numeric-id":1315831,"id":"Q1315831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c8390a96664d78d07b2aa2996a74fbe2077e566","datavalue":{"value":{"amount":"+0.913894","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$772D2741-F029-4539-B1F3-073814DDEDCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a027f29b3a1e20aa7f2ad66f89128ad7aa90236d","datavalue":{"value":{"entity-type":"item","numeric-id":5898540,"id":"Q5898540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ad711777e9564c8d07c5c69b6a5c2cdd85f4b90","datavalue":{"value":{"amount":"+0.91263556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$F7EDA81E-BA1A-4EE4-8D50-4E1FDF70684F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00c25e03c60bae296ad08a8a04e944c772534ea7","datavalue":{"value":{"entity-type":"item","numeric-id":2385450,"id":"Q2385450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ad711777e9564c8d07c5c69b6a5c2cdd85f4b90","datavalue":{"value":{"amount":"+0.91263556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$B085308D-02D5-40C6-AA67-BD7F3542B188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df6293fadaad389add09b0f160dfa0dddb68ef4e","datavalue":{"value":{"entity-type":"item","numeric-id":1350509,"id":"Q1350509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d1d75734909c0fa7e2e66dd9811c7101cc3dff8","datavalue":{"value":{"amount":"+0.90244365","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$DD58B77D-2E3F-4F52-B8C0-8D4AC779BD04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ca50459bc99e82a6914701c8792ff21fa2d190f","datavalue":{"value":{"entity-type":"item","numeric-id":4525283,"id":"Q4525283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62d50c8fafef7496161791182121747d67757887","datavalue":{"value":{"amount":"+0.89923763","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$6B6CDFB3-F9DA-4EDD-8564-4BAA0A7D1E53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"562eac86dfb4416d4bd960e7e6cb04d50066fc9f","datavalue":{"value":{"entity-type":"item","numeric-id":636314,"id":"Q636314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae563abdd111e3c16320e2056287c725306c8b3a","datavalue":{"value":{"amount":"+0.89321125","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$89F57150-F60F-4DC9-8A52-7F4572A96218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b02fc15a62bafa14b0b36824e7388f205c26ff9","datavalue":{"value":{"entity-type":"item","numeric-id":944387,"id":"Q944387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02985948bef8321d5d212a919736fed991a0622b","datavalue":{"value":{"amount":"+0.89042044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$F981CDB6-699C-4643-BD57-68BFAB0A3AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3858e1634101a8fbbcdac056ef503d49e96eb9b","datavalue":{"value":{"entity-type":"item","numeric-id":5884936,"id":"Q5884936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28c64a8541b852aa00bc6bfd41f44bcdf9ceed17","datavalue":{"value":{"amount":"+0.8887253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$F0D3A6EB-68EB-475C-9697-27A6067A9640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"133a05bb46988892d52757233f280a5aa5d3a954","datavalue":{"value":{"entity-type":"item","numeric-id":3735691,"id":"Q3735691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f630483c26d01626684dd33fca6707f5eef22bc9","datavalue":{"value":{"amount":"+0.88847506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1119628$0A68CBEB-36C9-44B6-827C-86DBCC1E7FC6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An arithmetical hierarchy in propositional dynamic logic","badges":[]}}}}}