TitleSome exponential lower bounds on formula-size in modal logic
AuthorsVan Ditmarsch, Hans
Fan, Jie
Van Der Hoek, Wiebe
Iliev, Petar
AffiliationCNRS, LORIA, Universit?? de Lorraine, France
Department of Philosophy, Peking University, China
Department of Computer Science, University of Liverpool, United Kingdom
Issue Date2014
Citation10th Conference on Advances in Modal Logic, AiML 2014.Groningen, Netherlands,10(139-157).
AbstractWe present two families of exponential lower bounds on the size of modal formulae and use them to establish the following succinctness results. We show that the logic of contingency (ConML) is exponentially more succinct than basic modal logic (ML).We strengthen the known proofs that the so-called public announcement logic (PAL) in a signature containing at least two different diamonds and one propositional symbol is exponentially more succinct than ML by showing that this is already true for signatures that contain only one diamond and one propositional symbol. As a corollary of these results, we obtain an alternative proof of the fact that modal circuits are exponentially more succinct than ML-formulae.
Appears in Collections:哲学系(宗教学系)

Files in This Work
There are no files associated with this item.

Web of Science®

Checked on Last Week


Checked on Current Time

License: See PKU IR operational policies.