Symbolic model checking for Dynamic Epistemic Logic — S5 and beyond. (22nd November 2017)

• Record Type: Journal Article
• Authors: van Benthem, Johan; van Eijck, Jan; Gattinger, Malvin; Su, Kaile
• Is Part Of: Journal of logic and computation. Volume 28:Number 2(2018)
• Page Start: 367
• Page End: 402
• Publication Date: 2017-11-22
• Subjects: Symbolic model checking -- Dynamic Epistemic Logic -- knowledge representation -- binary decision diagrams -- Muddy Children -- Russian Cards; Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exx038
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: Dynamic Epistemic Logic (DEL) can model complex information scenarios in a way that appeals to logicians. However, existing DEL implementations are ad-hoc, so we do not know how the framework really performs. For this purpose, we want to hook up with the best available model checking and SAT techniques in computational logic. We do this by first providing a bridge: a new faithful representation of DEL models as so-called knowledge structures that allow for symbolic model checking. For more complex epistemic change we introduce knowledge transformers analogous to action models. Next, we show that we can now solve well-known benchmark problems in epistemic scenarios much faster than with existing methods for DEL. We also compare our approach to model checking for temporal logics. Finally, we show that our method is not just a matter of implementation, but that it raises significant issues about logical representation and update.