We analyze some aspects of Independence-Friendly (IF) logic, a logic of imperfect information. After a tour of the basics of IF logic, in Chapter 2 we introduce the notions of sentence-relevance and relevance, which are meant to describe a discrepancy between the semantics of IF logic and the intuitions underlying the notion of imperfect information. Relevance can be thought either as a property of quantifier prefixes or of incomplete synctactical trees; in both cases, we show that relevance can be characterized synctactically and in terms of signalling phenomena. The characterization yields a large scheme of equivalence rules, which generalizes some earlier results. The theorem is also used to solve the open question of the expressive power of sentences with knowledge memory; this fragment turns out to be essentially first-order. In Chapter 3 we adapt the notion of relevance to equilibrium semantics (a probabilistic extension of IF logic) and prove that the characterization theorem still holds unvaried. Next we prove a result which partially describes the degree of freedom with which the probabilistic values may change when a statement of independence is added or removed. Instrumentally, we develop a different probabilistic semantics which is based on Skolem functions, and prove that it coincides with equilibrium semantics on finite structures. In Chapter 4 we analyze a segment of the literature on non-standard semantical interpretations of IF logic. Starting with the Subgame Semantics of Janssen, the systems we consider have in common the intent of falsifying a certain critical example, and of limiting in some ways the possibilities of coordination of the players of verification games. We add some new semantics, and also a synctactical extension of IF languages which is meant to express incomplete information about strategies. We compare all the systems in various ways. In Chapter 5 we extend a result of Sevenster, who gave a sufficient firstorderness criterion for prenex IF sentences, to the non-prenex case. We isolate four categories of sentences (Henkin, signalling, strictly signalling by disjunction, essential). The synctactical trees which correspond to the first two categories are proved to encode NP-complete model checking problems, while those in the fourth category are shown to be essentially first-order; more generally, IF trees are proved to fall either in the AC0 or the NP-complete class. We extend the first-orderness criterion to IF* logic (IF with independent connectives) and to extensions containing special sets of generalized quantifiers (in particular, the result covers all monotone quantifiers).

Standard and nonstandard semantics for languages of imperfect information

BARBERO, FAUSTO
2014-01-01

Abstract

We analyze some aspects of Independence-Friendly (IF) logic, a logic of imperfect information. After a tour of the basics of IF logic, in Chapter 2 we introduce the notions of sentence-relevance and relevance, which are meant to describe a discrepancy between the semantics of IF logic and the intuitions underlying the notion of imperfect information. Relevance can be thought either as a property of quantifier prefixes or of incomplete synctactical trees; in both cases, we show that relevance can be characterized synctactically and in terms of signalling phenomena. The characterization yields a large scheme of equivalence rules, which generalizes some earlier results. The theorem is also used to solve the open question of the expressive power of sentences with knowledge memory; this fragment turns out to be essentially first-order. In Chapter 3 we adapt the notion of relevance to equilibrium semantics (a probabilistic extension of IF logic) and prove that the characterization theorem still holds unvaried. Next we prove a result which partially describes the degree of freedom with which the probabilistic values may change when a statement of independence is added or removed. Instrumentally, we develop a different probabilistic semantics which is based on Skolem functions, and prove that it coincides with equilibrium semantics on finite structures. In Chapter 4 we analyze a segment of the literature on non-standard semantical interpretations of IF logic. Starting with the Subgame Semantics of Janssen, the systems we consider have in common the intent of falsifying a certain critical example, and of limiting in some ways the possibilities of coordination of the players of verification games. We add some new semantics, and also a synctactical extension of IF languages which is meant to express incomplete information about strategies. We compare all the systems in various ways. In Chapter 5 we extend a result of Sevenster, who gave a sufficient firstorderness criterion for prenex IF sentences, to the non-prenex case. We isolate four categories of sentences (Henkin, signalling, strictly signalling by disjunction, essential). The synctactical trees which correspond to the first two categories are proved to encode NP-complete model checking problems, while those in the fourth category are shown to be essentially first-order; more generally, IF trees are proved to fall either in the AC0 or the NP-complete class. We extend the first-orderness criterion to IF* logic (IF with independent connectives) and to extensions containing special sets of generalized quantifiers (in particular, the result covers all monotone quantifiers).
2014
Fausto Barbero
File in questo prodotto:
File Dimensione Formato  
FaustoBarbero Doctoral Thesis.pdf

Accesso riservato

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 947.23 kB
Formato Adobe PDF
947.23 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/142298
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact