{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T05:25:23Z","timestamp":1769577923404,"version":"3.49.0"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T00:00:00Z","timestamp":1769385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,1,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Though Propositional Dynamic Logic (PDL) as well as its relation to planning has been widely studied, there is as of yet no consensus as to how to handle parallelism in the framework. In this paper, we propose a parallel version of the Dynamic Logic of Propositional Assignments (${\\textsf{DL-PA} } $), a simple fragment of PDL in which atomic programs are assignments of the truth value of a formula to a propositional variable. We introduce two new operators for ${\\textsf{DL-PA} }$, namely parallel composition and inclusive non-deterministic composition. For the former, we suppose that two programs can be executed in parallel if they do not assign different values to the same variable. We give a polynomial translation of the resulting Dynamic Logic of Parallel Propositional Assignments (${\\textsf{DL-PPA} }$) into ${\\textsf{DL-PA} }$, thereby showing that complexity remains in PSpace. We then turn to planning and show how to capture executability of parallel STRIPS-like actions and solvability of planning tasks by parallel plans in ${\\textsf{DL-PPA} }$, following three different semantics for parallelism: one closely following our criterion for parallelism in ${\\textsf{DL-PPA} }$, and two from the literature based on interleaving.<\/jats:p>","DOI":"10.1093\/logcom\/exaf077","type":"journal-article","created":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T12:58:30Z","timestamp":1764680310000},"source":"Crossref","is-referenced-by-count":0,"title":["Simple dynamic logic with parallel composition and applications to planning"],"prefix":"10.1093","volume":"36","author":[{"given":"Andreas","family":"Herzig","sequence":"first","affiliation":[{"name":"IRIT, CNRS, University of Toulouse , 118 Route de Narbonne, 31062 Toulouse Cedex 9,","place":["France"]}]},{"given":"Fr\u00e9d\u00e9ric","family":"Maris","sequence":"additional","affiliation":[{"name":"IRIT, CNRS, University of Toulouse , 118 Route de Narbonne, 31062 Toulouse Cedex 9,","place":["France"]}]},{"given":"Elise","family":"Perrotin","sequence":"additional","affiliation":[{"name":"University of Bergen , Norway, P.O. Box 7803, NO-5020 Bergen,","place":["Norway"]}]},{"given":"Julien","family":"Vianey","sequence":"additional","affiliation":[{"name":"IRIT, CNRS, University of Toulouse , 118 Route de Narbonne, 31062 Toulouse Cedex 9,","place":["France"]}]}],"member":"286","published-online":{"date-parts":[[2026,1,27]]},"reference":[{"key":"2026012711402698200_ref1","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1093\/logcom\/exv035","article-title":"Iteration-free PDL with storing, recovering and parallel composition: a complete axiomatization","volume":"28","author":"Balbiani","year":"2018","journal-title":"Journal of Logic and Computation"},{"key":"2026012711402698200_ref2","doi-asserted-by":"crossref","first-page":"231","DOI":"10.3166\/jancl.13.231-276","article-title":"PDL with intersection of programs: a complete axiomatization","volume":"13","author":"Balbiani","year":"2003","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"2026012711402698200_ref3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1109\/LICS.2013.20","article-title":"Dynamic logic of propositional assignments: a well-behaved variant of PDL","volume-title":"28th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2013","author":"Balbiani","year":"2013"},{"key":"2026012711402698200_ref4","article-title":"DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE","author":"Balbiani"},{"key":"2026012711402698200_ref5","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1093\/logcom\/exu001","article-title":"Propositional dynamic logics for communicating concurrent programs with CCS\u2019s parallel operator","volume":"24","author":"Benevides","year":"2014","journal-title":"Journal of Logic and Computation"},{"key":"2026012711402698200_ref6","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.entcs.2011.03.008","article-title":"Propositional dynamic logic with storing, recovering and parallel composition","volume":"269","author":"Benevides","year":"2011","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"2026012711402698200_ref7","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0004-3702(96)00047-1","article-title":"Fast planning through planning graph analysis","volume":"90","author":"Blum","year":"1997","journal-title":"Artificial Intelligence"},{"key":"2026012711402698200_ref8","first-page":"445","article-title":"Better eager than lazy? How agent types impact the successfulness of implicit coordination","volume-title":"Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018","author":"Bolander","year":"2018"},{"key":"2026012711402698200_ref9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-030-38808-9_10","article-title":"Resource separation in dynamic logic of propositional assignments","volume-title":"Dynamic Logic. New Trends and Applications\u2014Second International Workshop, DaL\u00ed 2019, Porto, Portugal, October 7\u201311, 2019, Proceedings, Vol. 12005 of Lecture Notes in Computer Science","author":"Boudou","year":"2019"},{"key":"2026012711402698200_ref10","doi-asserted-by":"crossref","first-page":"100683","DOI":"10.1016\/j.jlamp.2021.100683","article-title":"Resource separation in dynamic logic of propositional assignments","volume":"121","author":"Boudou","year":"2021","journal-title":"Journal of Logical and Algebraic Methods in Programming"},{"key":"2026012711402698200_ref11","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0004-3702(94)90081-7","article-title":"The computational complexity of propositional STRIPS planning","volume":"69","author":"Bylander","year":"1994","journal-title":"Artificial Intelligence"},{"key":"2026012711402698200_ref12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.3233\/978-1-61499-672-9-193","article-title":"A simple account of multi-agent epistemic planning","volume-title":"ECAI 2016\u201422nd European Conference on Artificial Intelligence, 29 August\u20132 September 2016, The Hague, The Netherlands\u2014Including Prestigious Applications of Artificial Intelligence (PAIS 2016), Vol. 285 of Frontiers in Artificial Intelligence and Applications","author":"Cooper","year":"2016"},{"key":"2026012711402698200_ref13","doi-asserted-by":"crossref","first-page":"103437","DOI":"10.1016\/j.artint.2020.103437","article-title":"A lightweight epistemic logic and its application to planning","volume":"298","author":"Cooper","year":"2021","journal-title":"Artificial Intelligence"},{"key":"2026012711402698200_ref14","first-page":"1852","article-title":"When is temporal planning really temporal?","volume-title":"IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6\u201312, 2007","author":"Cushing","year":"2007"},{"key":"2026012711402698200_ref15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/3-540-63912-8_84","article-title":"Encoding planning problems in nonmonotonic logic programs","volume-title":"Recent Advances in AI Planning, 4th European Conference on Planning, ECP\u201997, Toulouse, France, September 24\u201326, 1997, Proceedings, Vol. 1348 of Lecture Notes in Computer Science","author":"Dimopoulos","year":"1997"},{"key":"2026012711402698200_ref16","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/BF01028975","article-title":"Parallel action: concurrent dynamic logic with independent modalities","volume":"51","author":"Goldblatt","year":"1992","journal-title":"Studia Logica"},{"key":"2026012711402698200_ref17","article-title":"Belief change operations: a short history of nearly everything, told in dynamic logic of propositional assignments","volume-title":"Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20\u201324, 2014","author":"Herzig","year":"2014"},{"key":"2026012711402698200_ref18","doi-asserted-by":"publisher","first-page":"228","DOI":"10.5591\/978-1-57735-516-8\/IJCAI11-049","article-title":"A dynamic logic of normative systems","volume-title":"IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16\u201322, 2011, IJCAI\/AAAI","author":"Herzig","year":"2011"},{"key":"2026012711402698200_ref19","doi-asserted-by":"publisher","first-page":"435","DOI":"10.3233\/978-1-61499-419-0-435","article-title":"On the revision of planning tasks","volume-title":"ECAI 2014\u201421st European Conference on Artificial Intelligence, 18\u201322 August 2014, Prague, Czech Republic\u2014Including Prestigious Applications of Intelligent Systems (PAIS 2014), Vol. 263 of Frontiers in Artificial Intelligence and Applications","author":"Herzig","year":"2014"},{"key":"2026012711402698200_ref20","doi-asserted-by":"publisher","first-page":"5576","DOI":"10.24963\/ijcai.2019\/774","article-title":"Dynamic logic of parallel propositional assignments and its applications to planning","volume-title":"Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10\u201316, 2019","author":"Herzig","year":"2019"},{"key":"2026012711402698200_ref21","doi-asserted-by":"crossref","DOI":"10.24963\/kr.2021\/68","article-title":"A dynamic epistemic logic with finite iteration and parallel composition","volume-title":"Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, November 2021","author":"Herzig","year":"2021"},{"key":"2026012711402698200_ref22","first-page":"98","article-title":"Generating parallel execution plans with a partial-order planner","volume-title":"Proceedings of the Second International Conference on Artificial Intelligence Planning Systems, University of Chicago, Chicago, Illinois, USA, June 13\u201315, 1994","author":"Knoblock","year":"1994"},{"key":"2026012711402698200_ref23","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(95)00095-X","article-title":"The complexity of PDL with interleaving","volume":"161","author":"Mayer","year":"1996","journal-title":"Theoretical Computer Science"},{"key":"2026012711402698200_ref24","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1145\/23005.23008","article-title":"Concurrent dynamic logic","volume":"34","author":"Peleg","year":"1987","journal-title":"Journal of the ACM"},{"key":"2026012711402698200_ref25","volume-title":"Lightweight Approaches to Reasoning about Knowledge and Belief","author":"Perrotin","year":"2021"},{"key":"2026012711402698200_ref26","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1016\/j.artint.2006.08.002","article-title":"Planning as satisfiability: parallel plans and algorithms for plan search","volume":"170","author":"Rintanen","year":"2006","journal-title":"Artificial Intelligence"},{"key":"2026012711402698200_ref27","volume-title":"Dynamic Logic of Propositional Assignments in the Polynomial Hierarchy, Draft","author":"Saffidine"},{"key":"2026012711402698200_ref28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0004-3702(00)00079-5","article-title":"Blocks world revisited","volume":"125","author":"Slaney","year":"2001","journal-title":"Artificial Intelligence"},{"key":"2026012711402698200_ref29","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1093\/logcom\/10.6.787","article-title":"A dynamic logic for acting, sensing, and planning","volume":"10","author":"Spalazzi","year":"2000","journal-title":"Journal of Logic and Computation"},{"key":"2026012711402698200_ref30","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1093\/jigpal\/jzu011","article-title":"PDL for structured data: a graph-calculus approach","volume":"22","author":"Veloso","year":"2014","journal-title":"Logic Journal of the IGPL"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/36\/2\/exaf077\/66591245\/exaf077.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/36\/2\/exaf077\/66591245\/exaf077.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T16:40:36Z","timestamp":1769532036000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exaf077\/8442296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,26]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,1,26]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaf077","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,3]]},"published":{"date-parts":[[2026,1,26]]},"article-number":"exaf077"}}