Generalized DEL-sequents

Guillaume Aucher (1) , Bastien Maubert (2) , François Schwarzentruber (1)

1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
2 S4 - System synthesis and supervision, scenarios

Let us consider a sequence of formulas providing partial information about an initial situation, about a set of events occurring sequentially in this situation, and about the resulting situation after the occurrence of each event. From this whole sequence, we want to infer more information, either about the initial situation, or about one of the events, or about the resulting situation after one of the events. Within the framework of Dynamic Epistemic Logic (DEL), we show that these different kinds of problems are all reducible to the problem of inferring what holds in the final situation after the occurrence of all the events. We then provide a tableau method deciding whether this kind of inference is valid. We implement it in LotrecScheme and show that these inference problems are NEXPTIME-complete. We extend our results to the cases where the accessibility relation is serial and reflexive and illustrate them with the coordinated attack problem.

Considérons une séquence de formules fournissant une information partielle à propos d'une situation initiale, d'un ensemble d'évènements se produisant séquentiellement dans cette situation, et de la situation résultante après l'occurence de chaque évènement. De cette séquence, nous voulons déduire plus d'information, soit sur la situation initiale, soit sur l'un des évènements, soit sur la situation résultante après l'un des évènements. Dans le cadre de la logique épistémique dynamique (DEL), nous montrons que ces diffŕentes sortes de problèmes sont tous réductibles au problème de déduire des propriétés de la situation finale après l'occurrence de tous les évèvenements. Nous fournissons ensuite une méthode tableau qui décide la validité de ce type d'inférence. Nous l'implémentons en LotrecScheme et prouvons que ces problèmes d'inférence sont NEXPTIME-complets. Nous étendons nos résultats aux cas où la relation d'accessibilité est sériale ou réflexive et les illustrons par le problème de l'attaque coordinée.

Domaines: Logique en informatique [cs.LO]; Système multi-agents [cs.MA]

Guillaume Aucher, Bastien Maubert, François Schwarzentruber. Generalized DEL-sequents. [Research Report] RR-8012, INRIA. 2012, pp.23. ⟨hal-00716074⟩