Logo image
Back
Dynamic logic of propositional assignments: A well-behaved variant of PDL
Conference proceeding   Peer reviewed

Dynamic logic of propositional assignments: A well-behaved variant of PDL

Philippe Balbiani, Andreas Herzig and Nicolas Troquard
28th Annual IEEE/ACM Symposium on Logic in Computer Science (LICS), 2013: 25 - 28 June 2013, New Orleans, Louisiana, pp.143-152
28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2013) (New Orleans, LA, 25/06/2013 - 28/06/2013)
01/01/2013
DOI: https://doi.org/10.1109/LICS.2013.20
Handle:
https://hdl.handle.net/10863/15478

Abstract

We study a version of Propositional Dynamic Logic (PDL) that we call Dynamic Logic of Propositional Assignments (DL-PA). The atomic programs of DL-PA are assignments of propositional variables to true or to false. We show that DL-PA behaves better than PDL, having e. g. compactness and eliminability of the Kleene star. We establish tight complexity results: both satisfiability and model checking are EXPTIME-complete.
url
http://lics.siglog.org/lics13/View
url
https://ieeexplore.ieee.org/abstract/document/6571546View

Details

Metrics

17 Record Views