Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWeakly Aggregative Modal Logic: Characterization and Interpolation (new version)
125
0
0.0
(
0
)
Added by
Jixin Liu
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Weakly Aggregative Modal Logic (WAML) is a collection of disguised polyadic modal logics with n-ary modalities whose arguments are all the same. WAML has some interesting applications on epistemic logic and logic of games, so we study some basic model theoretical aspects of WAML in this paper. Specifically, we give a van Benthem-Rosen characterization theorem of WAML based on an intuitive notion of bisimulation and show that each basic WAML system K_n lacks Craig Interpolation.
rate research
Read More
Quantified modal logic provides a natural logical language for reasoning about modal attitudes even while retaining the richness of quantification for referring to predicates over domains. But then most fragments of the logic are undecidable, over many model classes. Over the years, only a few fragments (such as the monodic) have been shown to be decidable. In this paper, we study fragments that bundle quantifiers and modalities together, inspired by earlier work on epistemic logics of know-how/why/what. As always with quantified modal logics, it makes a significant difference whether the domain stays the same across worlds, or not. In particular, we show that the bundle $forall Box$ is undecidable over constant domain interpretations, even with only monadic predicates, whereas $exists Box$ bundle is decidable. On the other hand, over increasing domain interpretations, we get decidability with both $forall Box$ and $exists Box$ bundles with unrestricted predicates. In these cases, we also obtain tableau based procedures that run in PSPACE. We further show that the $exists Box$ bundle cannot distinguish between constant domain and increasing domain interpretations.
The Poison Game is a two-player game played on a graph in which one player can influence which edges the other player is able to traverse. It operationalizes the notion of existence of credulously admissible sets in an argumentation framework or, in graph-theoretic terminology, the existence of non-trivial semi-kernels. We develop a modal logic (poison modal logic, PML) tailored to represent winning positions in such a game, thereby identifying the precise modal reasoning that underlies the notion of credulous admissibility in argumentation. We study model-theoretic and decidability properties of PML, and position it with respect to recently studied logics at the cross-road of modal logic, argumentation, and graph games.
We introduce a modal logic for describing statistical knowledge, which we call statistical epistemic logic. We propose a Kripke model dealing with probability distributions and stochastic assignments, and show a stochastic semantics for the logic. To our knowledge, this is the first semantics for modal logic that can express the statistical knowledge dependent on non-deterministic inputs and the statistical significance of observed results. By using statistical epistemic logic, we express a notion of statistical secrecy with a confidence level. We also show that this logic is useful to formalize statistical hypothesis testing and differential privacy in a simple and abstract manner.
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also show that for every class C of finite structures that can be expressed in MSO and is closed under homomorphisms, and for all integers l,k, there exists a *canonical* Datalog program Pi of width (l,k), that is, a Datalog program of width (l,k) which is sound for C (i.e., Pi only derives the goal predicate on a finite structure A if A is in C) and with the property that Pi derives the goal predicate whenever *some* Datalog program of width (l,k) which is sound for C derives the goal predicate. The same characterisations also hold for Guarded Second-order Logic (GSO), which properly extends MSO. To prove our results, we show that every class C in GSO whose complement is closed under homomorphisms is a finite union of constraint satisfaction problems (CSPs) of countably categorical structures.
Term modal logics (TML) are modal logics with unboundedly many modalities, with quantification over modal indices, so that we can have formulas of the form $exists y. forall x. (Box_x P(x,y) supsetDiamond_y P(y,x))$. Like First order modal logic, TML is also notoriously undecidable, in the sense that even very simple fragments are undecidable. In this paper, we show the decidability of one interesting fragment, that of two variable TML. This is in contrast to two-variable First order modal logic, which is undecidable.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
