| Fondations logiques des jeux à information imparfaite : stratégies uniformes (Logical foundations of games with imperfect information : uniform strategies) Maubert, Bastien - (2014-01-17) / Université de Rennes 1 - Fondations logiques des jeux à information imparfaite : stratégies uniformes
| |||
Langue : Anglais Directeur(s) de thèse: Pinchinat, Sophie; Aucher, Guillaume Discipline : Informatique Laboratoire : IRISA Ecole Doctorale : Mathématiques, informatique, signal, électronique et télécommunications Classification : Informatique Mots-clés : Théorie des jeux, Logique, Théorie des automates mathématiques
| |||
Résumé : There are in the literature many examples of games where the desired strategies are submitted to ''transversal'' constraints involving sets of plays, related by some semantic relation. The most famous example is strategies for games with imperfect information, and games where the objective involves some epistemic aspect provide many more examples. Nevertheless, to the best of our knowledge, there has been no thorough study on this type of constraints in their generality. This is what this thesis intends to start. Therefore, we define a general notion of uniform strategies. Uniformity properties of strategies are expressed in a logical language that extends CTL∗ with two original quantifiers. These quantifiers are very close to the classic knowledge operators of epistemic logics, and they involve sets of plays related by binary relations. We show how this notion of uniform strategies captures the known examples from the literature, and we study in depth the problem of uniform strategy synthesis, assuming that the binary relations between plays can be recognized by finite automata (rational relations). We establish several decidability and complexity results, relying widely on automata techniques: in particular, we introduce as tools jumping tree automata and information sets automata. Moreover, our results enable us to improve existing results and establish new ones, in the domains of model checking epistemic temporal logics, and epistemic planning. Abstract : There are in the literature many examples of games where the desired strategies are submit-ted to ''transversal'' constraints involving sets of plays, related by some semantic relation. The most famous example is strategies for games with imperfect information, and games where the objective involves some epistemic aspect provide many more examples. Nevertheless, to the best of our knowledge, there has been no thorough study on this type of constraints in their generality. This is what this thesis intends to start. Therefore, we define a general notion of uniform strategies. Uniformity properties of strategies are expressed in a logical language that extends CTL∗ with two original quantifiers. These quantifiers are very close to the classic knowledge operators of epistemic logics, and they involve sets of plays related by binary relations. We show how this notion of uniform strategies captures the known examples from the literature, and we study in depth the problem of uniform strategy synthesis, assuming that the binary relations between plays can be recognized by finite automata (rational relations). We establish several decidability and complexity results, relying widely on automata techniques: in particular, we introduce as tools jumping tree automata and information sets automata. Moreover, our results enable us to improve existing results and establish new ones, in the domains of model checking epistemic temporal logics, and epistemic planning. | |||