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).

`http://hdl.handle.net/2318/142298`

Titolo: | Standard and nonstandard semantics for languages of imperfect information |

Autori interni: | BARBERO, FAUSTO |

Autori: | Fausto Barbero |

Data di pubblicazione: | 2014 |

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). |

Appare nelle tipologie: | 07R-Tesi di Dottorato |

###### File in questo prodotto:

File | Descrizione | Dimensione | Formato | Tipologia | Licenza | |
---|---|---|---|---|---|---|

FaustoBarbero Doctoral Thesis.pdf | 947.23 kB | Adobe PDF | 1 Ver. finale autore | Utenti riconosciuti |

###### Citazioni

- PubMed Central