Inproceedings3205

PublikationenPublications

• Nach AutorBy Author
  • Bartosz BednarczykBartosz Bednarczyk
• Nach ForschungsgruppeBy Research Group
  • Computational LogicComputational Logic

Toggle side column

Why propositional quantification makes modal logics on trees robustly hard ?

Bartosz BednarczykBartosz Bednarczyk,  Stéphane DemriStéphane Demri

Bartosz Bednarczyk, Stéphane Demri
Why propositional quantification makes modal logics on trees robustly hard ?
LICS 2019, June 2019

• Details
• Bibtex

• KurzfassungAbstract
  Adding propositional quantification to the modal logics K, T or S4 is known to lead to undecidability but CTL with propositional quantification under the tree semantics (QCTL t ) admits a non-elementary Tower-complete satisfiability problem. We investigate the complexity of strict fragments of QCTL t as well as of the modal logic K with propositional quantification under the tree semantics. More specifically, we show that QCTL t restricted to the temporal operator EX is already Tower-hard, which is unexpected as EX can only enforce local properties. When QCTL t restricted to EX is interpreted on N-bounded trees for some N ≥ 2, we prove that the satisfiability problem is AExppol - complete; AExppol -hardness is established by reduction from a recently introduced tiling problem, instrumental for studying the model-checking problem for interval temporal logics. As consequences of our proof method, we prove Tower-hardness of QCTL t restricted to EF or to EXEF and of the well-known modal logics K, KD, GL, S4, K4 and D4, with propositional quantification under a semantics based on classes of trees.
• Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{DBLP:conf/lics/BednarczykD19,
  author    = {Bartosz Bednarczyk and
               St{ \'{e}}phane Demri},
  title     = {Why Propositional Quantification Makes Modal Logics on Trees Robustly
               Hard?},
  booktitle = {34th Annual {ACM/IEEE} Symposium on Logic in Computer Science, {LICS}
               2019, Vancouver, BC, Canada, June 24-27, 2019},
  pages     = {1--13},
  year      = {2019},
  crossref  = {DBLP:conf/lics/2019},
  url       = {https://doi.org/10.1109/LICS.2019.8785656},
  doi       = {10.1109/LICS.2019.8785656},
  timestamp = {Wed, 25 Sep 2019 18:03:36 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/lics/BednarczykD19},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}