Explicit Representations of Persistency for Propositional Action Theories
Résumé
We consider enriching the representation of actions in propositional logic by syntactic operators for representing the persistency of variables. This is motivated by the fact that the frame problem is not satisfactorily solved by propositional languages, such as binary decision diagrams or DNF. We introduce two such operators, allowing to represent different kinds of persistency, and consider the languages obtained from propositional logic by adding them at any level of nesting. We study the resulting languages from the point of view of their relative succinctness and the complexity of deciding successorship. We show an interesting picture of diverse complexity results.
Nous envisageons d'enrichir la représentation des actions en logique propositionnelle par des opérateurs syntaxiques pour représenter la persistance des variables. Ceci est motivé par le fait que le problème du cadre n'est pas résolu de manière satisfaisante par les langages propositionnels, tels que les diagrammes de décision binaires ou DNF. Nous introduisons deux de ces opérateurs, permettant de représenter différents types de persistance, et considérons les langages obtenus à partir de la logique propositionnelle en les ajoutant à n'importe quel niveau d'imbrication. Nous étudions les langages résultantes du point de vue de leur concision relative et de la complexité de la décision de successeur. Nous montrons une image intéressante de divers résultats de complexité.
Origine : Fichiers produits par l'(les) auteur(s)