{"entities":{"Q801682":{"pageid":803530,"ns":120,"title":"Item:Q801682","lastrevid":64442514,"modified":"2026-04-11T19:53:47Z","type":"item","id":"Q801682","labels":{"en":{"language":"en","value":"The propositional dynamic logic of deterministic, well-structured programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3880103"}},"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":"Q801682$C49AD614-7491-48DC-8148-378A36DC3958","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b500a59e1cefa8dc93df0725c7ef1a59fdbcd99","datavalue":{"value":{"text":"The propositional dynamic logic of deterministic, well-structured programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q801682$92E32045-0D98-489E-96A1-F8960EC7ED45","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4bb3408bbb5c912f1ce0980b6d0b2eebf93d25e1","datavalue":{"value":"0552.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$0ECE7A01-0728-488C-ACA6-C2D9217FFF87","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc0b2fd79694de04aba0ad903efc6af4eef03913","datavalue":{"value":"10.1016/0304-3975(83)90097-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$F3B79FE8-A444-41B2-A9A8-C3835D22CF9C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ddea5ba0eeb9138fb9e2a8de5e2cddb8c80bf84a","datavalue":{"value":{"entity-type":"item","numeric-id":272148,"id":"Q272148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$393DC53A-CE41-4AC5-8D90-51A522C3AEA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cdf21d0e331a47790f86a0203b4b15950c2a72f","datavalue":{"value":{"entity-type":"item","numeric-id":537850,"id":"Q537850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$37ED156C-A7C0-4639-BBC5-AC2E1915D205","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":"Q801682$DF3C62B1-FA95-4571-88C3-7BD76E95C559","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":"Q801682$ED325BBD-EB39-4FB4-BF5C-09CB83B536BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1d0d99bc68c5fb6beeae46079b080405419c77fa","datavalue":{"value":"PDL is the propositional dynamic logic of regular programs. DPDL is the propositional dynamic logic of regular programs built from deterministic atomic programs. SDPDL is the propositional dynamic logic of deterministic well-structured programs, i.e., programs that are built from deterministic atomic programs by means of the while and if constructs. The main results of the paper are that SDPDL is strictly less expressive than DPDL, and that the validity problem for SDPDL is logspace complete for PSPACE (the validity problems for PDL and DPDL are logspace complete for EXPTIME). The results carry a special significance, since they indicate that the exponential lower bound by Fischer and Ladner for PDL may not be all that realistic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$1DE7969F-BEC3-4C47-8A9D-0D79B9592DB2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$87863053-C754-4684-B5D1-BFEDE4A56D8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$05428712-E030-4CB9-9580-E850289684F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$4959D493-0595-4DB7-A1DC-D69CC1D461BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$6E300D36-C05C-4EA3-A403-D2BEFC7E4F20","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"240a61ebe08ee0b11d05229e61bb262d3ceba5a8","datavalue":{"value":"3880103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$09EEAD2B-D110-43A7-B72A-21DF7676C35B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52ba6d968a7617d9b56b80603a9b30974da2b918","datavalue":{"value":"determinism","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$7A078FEE-5E8C-4571-8D17-432E6EEA742A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb79299daf8f29391d6c8a2b4222865ffe474551","datavalue":{"value":"decision procedure","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$F7D1EF3E-0EB0-4494-B6DE-5C9DD1B21BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78e469cb56ef748b3f9619abee5f10dfa052a7b9","datavalue":{"value":"expressiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$817F3AE7-C030-4893-B511-D700B286A42D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cc4d43671892ebbacba377d7e7fd29b3c176a03","datavalue":{"value":"polynomial space completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$8BA481DE-06D7-4AFE-BC8A-A2FAF05D4FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f53e9af042b6aae786a649b21f8510f7a952210e","datavalue":{"value":"regular programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$129ADFE7-13B4-4D23-8583-EACB6499F621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a5eef9a7839e51aae1829128fd74061b3797fc5","datavalue":{"value":"propositional dynamic logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$51814D43-3377-4A0B-BB02-9D86834C5758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ee74a805c465b84afa5591a4b3ca24b820801d5","datavalue":{"value":"well- structured programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$018EE0FC-FF96-45EB-BC91-3CEDF977AA0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bfd503ee6f3c6434a4ba5a5daef05ea995bab4e","datavalue":{"value":"validity problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q801682$87ED3BC3-8C84-490A-B4D0-561ECF161FE7","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":"Q801682$8BF6CA72-D825-42FA-9448-5B03D7BA9D08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad21928bd542446f4dab874e018db82a98381684","datavalue":{"value":{"entity-type":"item","numeric-id":1839245,"id":"Q1839245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$24652E45-CF8B-4C67-946B-8B0E3260F097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3107ddcd298359b712f21dd5530eda3720b9652","datavalue":{"value":{"entity-type":"item","numeric-id":3957927,"id":"Q3957927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$B940CCE9-B617-40B2-991B-85EA83BD92C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3816ffbdb7e402ef6b808924a771f4b406e6572","datavalue":{"value":{"entity-type":"item","numeric-id":4746782,"id":"Q4746782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$5F2D07DE-B3D0-411A-B4E1-BC124577920D","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":"Q801682$2FE0B070-E6F0-4DCF-81FE-E68CC1E48F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac3af2a5d6d90fc35dbcdf27c89fba0731ef592c","datavalue":{"value":{"entity-type":"item","numeric-id":1233308,"id":"Q1233308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$2F8DBA86-FB25-4F2C-A5E2-081BFAC67823","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":"Q801682$B8BE238A-1B43-4C6F-8362-CEF718C9EABB","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":"Q801682$81C91F51-AD0E-468C-AFE5-DEED9FA0E7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b153c8c27841e1303134abcef0ca02f0dc5006f8","datavalue":{"value":{"entity-type":"item","numeric-id":3968454,"id":"Q3968454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$50B9A4D4-AC05-456E-84D7-32321812C730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3de510ed3fd05142f0bf32ec55ad85ebc17090f2","datavalue":{"value":{"entity-type":"item","numeric-id":1161284,"id":"Q1161284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$2FBB1013-61A7-4153-BF60-469BA587F227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bde352de7529b3727f2dfe868ebf2842f0d7ff8","datavalue":{"value":{"entity-type":"item","numeric-id":5626601,"id":"Q5626601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$13062E7D-B851-480A-BAD7-E8443FB1D31B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efd44a74ba2cf90ff6508831ecc35c7d31b4b278","datavalue":{"value":{"entity-type":"item","numeric-id":4748128,"id":"Q4748128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$D4A8D2AE-E3CB-4A76-9441-2E391AF78B8F","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":"Q801682$794BED5C-3D63-4884-916A-73F6C0D7254D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"856fa123dbdb98ef62ecff7e9dcf6388514f3caf","datavalue":{"value":{"entity-type":"item","numeric-id":3953158,"id":"Q3953158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$50079F47-FD48-47AB-90B3-5387CD30650F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c417924a46f5e00f10bb7b003d8951d6cdf42c1","datavalue":{"value":{"entity-type":"item","numeric-id":5596237,"id":"Q5596237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$C9420D2F-C934-4C57-8662-6DEECADF7302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801682$C4B03E1F-6FE1-422D-8FC1-AEE3CFB83E6B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"faf5466aa233cbd9d1beec7d0551eeeb2c3e8156","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90097-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q801682$C23E6D59-A938-4B76-A1F0-EFA2D34E5AC3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"76da81c6cd63530f4bcfba5cbbc8ed540c6ac408","datavalue":{"value":"W2101982422","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801682$A96DD5E9-A156-44F6-A0A2-D4D0D496FAFE","rank":"normal"}],"P1643":[{"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":"45a708fec8e28b27aee5f35acde24520d335cafc","datavalue":{"value":{"amount":"+0.8568058609962463","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":"Q801682$7F43A756-AE05-4776-B221-8FF63174B4EA","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":"0a5a1c6827dc97572d240061d68704f28b484698","datavalue":{"value":{"amount":"+0.8558548092842102","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":"Q801682$DB3486E1-12B9-4E58-83E8-15F2505BB2B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8227c58f50fa9702c619efa5e6b3509692ae1975","datavalue":{"value":{"entity-type":"item","numeric-id":5899095,"id":"Q5899095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77ca60983a36363d2bae4b879b449c31a54d6a85","datavalue":{"value":{"amount":"+0.8492853045463562","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":"Q801682$A60F6C03-8895-4EBD-8916-6A5793AA2846","rank":"normal"},{"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":"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":"Q801682$00317374-4099-47F2-89C3-554A4EEDF983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01d6601fc86f6b43686b1d40f4a27b351705473b","datavalue":{"value":{"entity-type":"item","numeric-id":3897033,"id":"Q3897033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf0b2fa92b8565547b09d78cf6c6aa5a12f52688","datavalue":{"value":{"amount":"+0.8467439413070679","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":"Q801682$6857A362-5949-4672-A1E2-0B9D77BF80C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The propositional dynamic logic of deterministic, well-structured programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_propositional_dynamic_logic_of_deterministic,_well-structured_programs"}}}}}