Sergej Scheck (GREYC, Caen)

Computational efficiency of a planner in automated planning depends among other things on the formal representation of actions. This motivates the study of the relative succinctness and complexity of queries for languages that can be used to represent actions. We are going to investigate variants of two most common representations, namely the boolean formulas and the planning domain description language PDDL. We will also investigate the complexity of checking whether one state is a possible successor of another state via a given action.