Université de Rennes 1 Fondations logiques des jeux à information imparfaite : stratégies uniformes Logical foundations of games with imperfect information : uniform strategies Théorie des jeuxLogiqueThéorie des automates mathématiques Game theoryLogicMachine theory Théorie des jeux Thèses et écrits académiques Automates mathématiques, Théorie des Thèses et écrits académiques 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. 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. Electronic Thesis or DissertationText en application/force-download1 : 1375 Kohttp://ecm.univ-rennes1.fr/nuxeo/site/esupversions/8a2c0577-4b8d-48d9-95de-900bcee9cb03 Maubert Bastien 1987-02-26 FR 177808756 bastien.maubert@gmail.com 2014REN1S001 http://www.theses.fr/2014REN1S001 2014-01-17 Informatique Université de Rennes 1thesis.degree.grantor_1 02778715X Doctorat non ouiPinchinatSophieintervenant_1097578754AucherGuillaumeintervenant_2131047418 Mathématiques, informatique, signal, électronique et télécommunicationsecoleDoctorale_1 139007164 Université européenne de BretagnepartenaireRecherche_1 139075119 IRISApartenaireRecherche_2 026386909 ddc:004 PinchinatSophieAucherGuillaumeUniversité de Rennes 1Sciences et technologie, médecine, pharmacie, odontologie, droit, économie, gestion, philosophieMathématiques, informatique, signal, électronique et télécommunicationsÉcole doctorale Mathématiques, informatique, signal, électronique et télécommunications (Rennes)Université européenne de Bretagne Pôle de recherche et d'enseignement supérieur de Bretagne IRISA ASCII PDF 1407772