| Complexité théorique du raisonnement en logique épistémique dynamique et étude d’une approche symbolique (Theoretical complexity of reasoning in dynamic epistemic logic and study of a symbolic approach) Charrier, Tristan - (2018-12-05) / Universite de Rennes 1 - Complexité théorique du raisonnement en logique épistémique dynamique et étude d’une approche symbolique
| |||
Langue : Anglais Directeur(s) de thèse: Pinchinat, Sophie Discipline : informatique Laboratoire : IRISA Ecole Doctorale : MATHSTIC Classification : Informatique Mots-clés : système multi-agents, vérification de modèles, logique épistémique, complexité de calcul, modèle symbolique, planification épistémique
| |||
Résumé : Nous étudions la complexité théorique de tâches de raisonnement mettant en jeu la connaissance des agents dans les systèmes multi-agents. Nous considérons la logique épistémique dynamique (DEL) comme une façon naturelle d'exprimer la connaissance, qui permet d'exprimer la connaissance d'ordre supérieur des agents et des actions dynamiques partiellement observées. Nous montrons des résultats de complexité algorithmique pour la vérification de modèles et la satisfiabilité de formules de DEL, et définissons une approche symbolique pour ces mêmes problèmes. Nous étudions également la planification basée sur DEL ainsi que des quantifications sur certaines actions : les annonces publiques. Abstract : We study the theoretical complexity of reasoning tasks involving knowledge in multi-agent systems. We consider dynamic epistemic logic (DEL) as a natural way of expressing knowledge, which allows to express nested knowledge of agents and partially observed dynamic actions. We show complexity results for model checking and satisfiability of DEL formulas, and define a symbolic approach for these problems. We also study DEL-based planning and quantification over specific actions: public announcements. | |||