{"id":"arxiv/2603.05131","url":"https://arxiv.org/abs/2603.05131","tags":["cs.LO","math.LO"],"score":0,"title":"The Complexity of the Constructive Master Modality","domain":"cs.LO","source":"arxiv","authors":["Sofía Santiago-Fernández","David Fernández-Duque","Joost J. Joosten"],"reviews":0,"subject":"cs.LO","summary":"We introduce the semantically-defined constructive master-modality logics $\\sf CK^*$ and $\\sf WK^*$, extending the basic constructive modal logic $\\sf CK$ and the Wijesekera-style logic $\\sf WK$ obtained by impossing infallibility. Using translations between our logics and fragments of $\\sf PDL$, we show that both $\\sf CK^*$ and $\\sf WK^*$ are EXPTIME-complete and admit an exponential-size finite model property. In particular, for their diamond-free fragment, also studied by Afshari et al. and Celoni, we establish EXPTIME-completeness, thereby settling the conjecture of Afshari et al. As an…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-05","reactions":{}}