Standard and nonstandard semantics for languages of imperfect information

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