Losing connection: the modal logic of definable link deletion. (15th April 2020)

• Record Type: Journal Article
• Authors: Li, Dazhu
• Is Part Of: Journal of logic and computation. Volume 30:Number 3(2020)
• Page Start: 715
• Page End: 743
• Publication Date: 2020-04-15
• Subjects: Graph game -- modal logic -- dynamic logic -- link deletion -- undecidability; Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exz036
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: In this article, we start with a two-player game that models communication under adverse circumstances in everyday life and study it from the perspective of a modal logic of graphs, where links can be deleted locally according to definitions available to the adversarial player. We first introduce a new language, semantics and some typical validities. We then formulate a new type of first-order translation for this modal logic and prove its correctness. Then, a novel notion of bisimulation is proposed that leads to a characterization theorem for the logic as a fragment of first-order logic, and a further investigation is made of its expressive power against hybrid modal languages. Next, we discuss how to axiomatize this logic of link deletion, using dynamic-epistemic logics as a contrast. Finally, we show that our new modal logic lacks both the tree model property and the finite model property and that its satisfiability problem is undecidable.