Utilizza questo identificativo per citare o creare un link a questo documento:
|Titolo:||Standard and nonstandard semantics for languages of imperfect information|
|Autori interni:||BARBERO, FAUSTO|
|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:
|FaustoBarbero Doctoral Thesis.pdf||947.23 kB||Adobe PDF||1 Ver. finale autore||Utenti riconosciuti|
- PubMed Central loading...
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.