Logics and algebras for multiple players

Review of Symbolic Logic 3 (3):485-519 (2010)
  Copy   BIBTEX

Abstract

We study a generalization of the standard syntax and game-theoretic semantics of logic, which is based on a duality between two players, to a multiplayer setting. We define propositional and modal languages of multiplayer formulas, and provide them with a semantics involving a multiplayer game. Our focus is on the notion of equivalence between two formulas, which is defined by saying that two formulas are equivalent if under each valuation, the set of players with a winning strategy is the same in the two respective associated games. We provide a derivation system which enumerates the pairs of equivalent formulas, both in the propositional case and in the modal case. Our approach is algebraic: We introduce multiplayer algebras as the analogue of Boolean algebras, and show, as the corresponding analog to Stone’s theorem, that these abstract multiplayer algebras can be represented as concrete ones which capture the game-theoretic semantics. For the modal case we prove a similar result. We also address the computational complexity of the problem whether two given multiplayer formulas are equivalent. In the propositional case, we show that this problem is co-NP-complete, whereas in the modal case, it is PSPACE-hard

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Partial algebras for Łukasiewicz logics and its extensions.Thomas Vetterlein - 2005 - Archive for Mathematical Logic 44 (7):913-933.
Equational Reasoning in Non-Classical Logics.Marcelo Frias & Ewa Orlowska - 1998 - Journal of Applied Non-Classical Logics 8 (1-2):27-66.
Basic properties of the equivalence.Jacek K. Kabziński - 1982 - Studia Logica 41 (1):17-40.
Duality for algebras of relevant logics.Alasdair Urquhart - 1996 - Studia Logica 56 (1-2):263 - 276.
Free Łukasiewicz implication algebras.José Patricio Díaz Varela - 2008 - Archive for Mathematical Logic 47 (1):25-33.
Decidable and undecidable logics with a binary modality.ágnes Kurucz, István Németi, Ildikó Sain & András Simon - 1995 - Journal of Logic, Language and Information 4 (3):191-206.
The logic of Peirce algebras.Maarten De Rijke - 1995 - Journal of Logic, Language and Information 4 (3):227-250.

Analytics

Added to PP
2010-08-14

Downloads
111 (#147,534)

6 months
5 (#246,492)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Yde Venema
University of Amsterdam

Citations of this work

Game theoretical semantics for some non-classical logics.Can Başkent - 2016 - Journal of Applied Non-Classical Logics 26 (3):208-239.

Add more citations