Raisonnement sur les actions : de Toronto à AmsterdamReportar como inadecuado




Raisonnement sur les actions : de Toronto à Amsterdam - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Computer Science 2 IRIT - Institut de recherche en informatique de Toulouse

Résumé : Nous montrons comment en raisonnement sur les actions la fameuse solution de Reiter du problème du décor peut être modélisée en logique épistémique dynamique, et nous proposons une méthode de régression optimale. Notre méthode étend la solution de Reiter en intégrant des actions d-observation et des opérateurs modaux de connaissance, et traduit le formalisme de Reiter le Calcul des situations dans une logique des actions et des connaissances comprenant des opérateurs d-annonce et d-affectation. En étendant la méthode de réduction de Lutz de la logique des annonces publiques aux affectation, nous établissons des résultats de complexité pour la régression. Nous montrons que ces résultats sont optimaux : le problème de décider la satisfiabilité d-une formule est NP-complet pour un agent, PSPACE-complet pour plusieurs agents et EXPTIME-complet dans la présence de l-opérateur de connaissance commune. We show how in the propositional case Reiter-s well-known solution to the frame problem can be modelled in dynamic epistemic logic, and provide an optimal regression algorithm. Our method is as follows : we extend Reiter-s solution by integrating observation actions and modal operators of knowledge, and encode the resulting formalism in a dynamic epistemic logic with announcement and assignment operators. By extending Lutz- recent satisfiability-preserving reduction for public announcement logic to assignments, we establish optimal complexity results for regression : satisfiability is NP-complete for one agent, PSPACE-complete for multiple agents and EXPTIME-complete when common knowledge is involved.

Mots-clés : raisonnement sur les actions et changement logiques épistémique dynamique systèmes multi-agents régression reasoning about actions and change





Autor: Hans Van Dimarsch - Andreas Herzig - Tiago De Lima -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados