1,720,975 research outputs found
DECIDABILITY OF INDEPENDENCE-FRIENDLY MODAL LOGIC
No full textIn this paper we consider an independence-friendly modal logic, IFML. It follows from results in the literature that qua expressive power, IFML is a fragment of second-order existential logic, , that cannot be translated into first-order logic. It is also known that IFML lacks the tree structure property. We show that IFML has the ‘truncated structure property’, a weaker version of the tree structure property, and that its satisfiability problem is solvable in 2NEXP. This implies that this paper reveals a new decidable fragment of . We also show that IFML becomes undecidable if we add the identity symbol to its vocabulary by means of a reduction from the tiling problem.</jats:p
Linear Programming Tools for Analyzing Strategic Games of Independence-Friendly Logic and Applications
No full textThe complexity of Scotland Yard
No full textThis paper discusses a case study of the board game of Scotland Yard from a computational perspective. Interestingly, Scotland Yard is a genuine “playgame ” with imperfect information. For reasons not completely clear to me, games with imperfect information have escaped the interest of researchers in Algorithmic combinatorial gametheory. I show by means of a powerset argument, that Scotland Yard can also be considered a game of perfect information, that is surprisingly similar to the original game – up to isomorphism, that is. Using the powerset analysis, I show that Scotland Yard has PSPACEcomplete complexity be it with or without imperfect information. In fact, imperfect information may even simplify matters: if the cops are supposed to be consequently ignorant of Mr. X’s whereabouts throughout the game the complexity is ‘but ’ NP-complete.
Academy of Finland Abstract
No full textThe aim of the present paper is to discuss two different ways of formulating independence friendly (IF) modal logic. In one of them, first presented in [17] modifying ideas introduced in [4], the language of basic modal logic is enriched with the slash notation familiar from IF first-order logics, and the resulting logic is interpreted in terms of games and uniform strategies. The present paper formulates a different approach, by introducing a framework that can be used for formulating various IF modal logics. Within the framework, an IF modal logic is defined by imposing conditions on its structural relationships to other logics, namely a specified modal logic (for instance: basic modal logic), its first-order correspondence language, and IF logic. This framework makes it possible to obtain expressively strong languages that nevertheless enjoy ‘nice ’ properties. In this vein, the so-called ‘structurally determined IF modal logic ’ was introduced in [19]. We compare the logics emerging from these two approaches. More generally, the issue of the Eigenart of IF modal logics is addressed.
Henkinquantifiers:
No full textIn this paper, we study the game-theoretic and computational repercussions of Henkin’s partially ordered quantifiers [19]. After defining a gametheoretic semantics for these objects, we observe that tuning the parameter of absentmindedness gives rise to quantifier prefixes studied in [28]. In the interest of computation, we characterize the complexity class P NP � in terms of partially ordered quantifiers, by means of a proof different from Gottlob’s [17]. We conclude with some research questions at the interface of logic, game theory, and complexity theory
- …
