{"entities":{"Q1311976":{"pageid":1322726,"ns":120,"title":"Item:Q1311976","lastrevid":68429259,"modified":"2026-04-12T23:39:14Z","type":"item","id":"Q1311976","labels":{"en":{"language":"en","value":"\\(\\Pi_ 1^ 1\\)-universality of some propositional logics of concurrent programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 487966"}},"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":"Q1311976$FFD597BA-ACFA-49FA-88FD-026F08A8FE18","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"74d513d6fb9cc7437fa7093fbbbcde918e4333a5","datavalue":{"value":{"text":"\\(\\Pi_ 1^ 1\\)-universality of some propositional logics of concurrent programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1311976$0557C6C7-F089-48C0-8C73-CA80AC03C564","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b1fcfd55cfb4d4268b5c8c267c4927d770648dd0","datavalue":{"value":"0802.03026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1311976$971DF900-4469-499C-9D83-2D76173E5D07","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"46061317bbb51723274bb597d49fd4997e8bfe09","datavalue":{"value":"10.1016/0304-3975(93)90347-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1311976$D1F6356F-B086-4B72-A49A-041391F6F7C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a7878fa5494ad4c7a94bad7368d9bd02c152a60","datavalue":{"value":{"entity-type":"item","numeric-id":1311975,"id":"Q1311975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$7F88C193-EC48-40E3-946A-3DEDAF574ACA","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":"Q1311976$AAC4FCB4-65E4-4279-B78D-031D55D8BB4A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"031c5d066bfbf994f645c207439d2003ce1ed02e","datavalue":{"value":{"time":"+1994-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1311976$2851CE46-64B8-4619-8A46-FCAC8E7E390E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"96b5e52b650c426ce50141914a2ef555c9c77e58","datavalue":{"value":"The paper contributes to several known results on undecidability of propositional dynamic logics. Two variants of propositional dynamic logic for concurrent programs are proven highly undecidable. These variants are an extension of PDL by the asynchronous constructs shuffle and iterated shuffle (APDL), and a variant of PDL with a partial commutativity relation on primitive programs (CPDL). The validity problem for APDL and CPDL is proven to be \\(\\Pi^ 1_ 1\\)-universal. In both cases the proof is based on simulation of infinite computations of one-counter machines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$8255C50B-561B-42B1-8B8C-345F635CA5B6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1311976$DC44EE8D-57D1-46C5-B98F-0B4D8690F316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1311976$1A161C93-8B92-4654-84C3-F51AA8CE1DD9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bb20f6f38f20bc7fb04f0dae8951bf01b3134be4","datavalue":{"value":"487966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1311976$59A3FD8B-1B44-40D6-A6E2-B87A4ED6A096","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"445a4fbc6b6bbba6e3c2169de8e334950d4f0826","datavalue":{"value":"concurrency","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$2DE746CB-1D7B-498C-8FEA-C2299B1E2784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$4A83F218-AE43-4845-B714-1EC94108F8E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a5eef9a7839e51aae1829128fd74061b3797fc5","datavalue":{"value":"propositional dynamic logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$DAF5501F-F005-456E-A292-BCC5E3B8A711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2977bda8220ccceab9112dd54c73384bf0be45e3","datavalue":{"value":"iterated shuffle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$6D136802-A406-4C81-94B2-AF9E8A788AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a10b47f3d191b3c5bad349552e743bb482eaed3","datavalue":{"value":"partial commutativity relations on primitive programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$0819174E-31E7-4669-B47F-5A6A8726CADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c96c670cb5bb3f93d571a5f56f1e88c84388368c","datavalue":{"value":"validity problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$CD34A361-C992-496E-BA2E-8226BD048235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b2dbc7624deff4f1da4a6e69117270c9be2f974","datavalue":{"value":"infinite computations of one-counter machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1311976$1DAC52AF-C8FC-4A79-817F-9DE9F9880329","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"25306ed43a658ea19c64035347a11c5c173761c0","datavalue":{"value":{"entity-type":"item","numeric-id":282093,"id":"Q282093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$C0C98FCA-A885-4627-813C-5AA4635AB13D","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":"Q1311976$9B25CD3F-D878-4413-ABCF-77DF66D573C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb3f3d4284f29707c15dbffe01b4356eafdc3d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1107296,"id":"Q1107296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$9E17AA09-2D2E-4A72-B63D-F63222FB727A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd36197f8fd279b619e4ed6eeb98e09a53a656e7","datavalue":{"value":{"entity-type":"item","numeric-id":4187288,"id":"Q4187288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$944AF61F-5C24-4B05-B559-507BB5AC5FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97744e38548305e628b67361005256b1d8aea75f","datavalue":{"value":{"entity-type":"item","numeric-id":3922190,"id":"Q3922190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$CB0F8559-D5EF-4CD0-BF18-5F30392FCDD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"266e74dfc49b54318e6f3c94ba097b82b39ab983","datavalue":{"value":{"entity-type":"item","numeric-id":3947146,"id":"Q3947146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$8C6FD565-5B17-44A0-B0F6-30F2BAD16A72","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":"Q1311976$31ECE5B8-E48D-48D5-A2BA-127B79369A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fd1e28e0e6c158c9409c70c379bfcc7c9840573","datavalue":{"value":{"entity-type":"item","numeric-id":5576254,"id":"Q5576254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$8C7E2DB7-554D-475B-B41C-88FFC66CD196","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":"Q1311976$EB0EF486-0BE2-43B5-BB19-38DB689D1A11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"657452dbab5687b4165773cff8849d89f34ed4bf","datavalue":{"value":{"entity-type":"item","numeric-id":4140399,"id":"Q4140399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$A05573AF-B6EA-4EDB-B1FC-9471CF367601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"424d08897b475d265202ce6f9dd47074ed2a8284","datavalue":{"value":{"entity-type":"item","numeric-id":3923593,"id":"Q3923593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$964F8D69-68DA-4DEF-B238-D28B805B0970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1b26bdc210a3d291b796088837bddd84cce8b4c","datavalue":{"value":{"entity-type":"item","numeric-id":775202,"id":"Q775202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$F54308BE-F461-478D-8015-9599E265F5A8","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":"Q1311976$D4615FDF-7190-44D6-9B68-5698F0BCF8F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3e79c1198a5adad0b28f20fcd66d4c98012ceb6","datavalue":{"value":{"entity-type":"item","numeric-id":4162475,"id":"Q4162475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$4BD22BC8-BCF4-4F4C-9271-0550EC835BCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea3235163a762cb44bb2b482cf48af6fc69f890c","datavalue":{"value":{"entity-type":"item","numeric-id":3897033,"id":"Q3897033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1311976$FF54E26C-56F8-43FF-839E-DE2394B88733","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"789edbfedc483f4f27be291a26ad57f2645a94f9","datavalue":{"value":{"entity-type":"item","numeric-id":3801527,"id":"Q3801527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"855ec564bc49ef60f284d3e7a7fb7689911ebdde","datavalue":{"value":{"amount":"+0.805081307888031","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":"Q1311976$2BFC85AA-9FD9-4A9A-8CAA-36F3156D6CB2","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":"d61f8c491e569c28460ef3579b65ae9a4b76c522","datavalue":{"value":{"amount":"+0.7868363857269287","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":"Q1311976$A1041DEC-34AD-41B7-AD3A-0AF0833D4367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1696c4ca228238e4beb09001c17ecb040f1e3e7e","datavalue":{"value":{"entity-type":"item","numeric-id":3185762,"id":"Q3185762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30619a354a60e810e7a72ab171112484b68023e5","datavalue":{"value":{"amount":"+0.7798667550086975","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":"Q1311976$7BF47454-DE37-410A-AA63-26A944252665","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":"ce08610087fb014e5a4a38e32b853124ff9d66a3","datavalue":{"value":{"amount":"+0.7780390381813049","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":"Q1311976$A87AEC80-8869-4FC1-9CB7-6A08D4FE801B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b388380c6a9851a6fc43534a726a1804225b3bf7","datavalue":{"value":{"entity-type":"item","numeric-id":2946675,"id":"Q2946675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54153c69802fd05d53d6e87d15d96ada2bc0ac8a","datavalue":{"value":{"amount":"+0.7748921513557434","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":"Q1311976$102CAEA1-13E5-4DC0-98E9-446770DC1E48","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(\\Pi 1^ 1\\)-universality of some propositional logics of concurrent programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(%5CPi_1%5E_1%5C)-universality_of_some_propositional_logics_of_concurrent_programs"}}}}}