Skip to Main content Skip to Navigation
Conference papers

Knowledge Compilation for Action Languages

Sergej Scheck 1 Alexandre Niveau Bruno Zanuttini
1 Equipe MAD - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : We study different languages for representing nondeterministic actions in automated planning from the point of view of knowledge compilation. Precisely, we consider succintness issues (how succinct is the description of an action in each language?) and complexity issues (how hard is it to decide whether a state is a successor of another one through some action described in one of these languages?). We study an abstract, nondeterministic version of PDDL, the language of NNF action theories, and DL-PPA, the dynamic logic of parallel propositional assignments. We show that these languages have different succinctness and different complexity of queries: DL-PPA is the most succinct one and NNF is the least succinct, and deciding successorship is already NP-complete for nondeterministic PDDL.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download
Contributor : Bruno Zanuttini <>
Submitted on : Thursday, October 22, 2020 - 12:19:54 AM
Last modification on : Friday, October 23, 2020 - 3:31:24 AM
Long-term archiving on: : Saturday, January 23, 2021 - 6:11:10 PM


Publisher files allowed on an open archive


  • HAL Id : hal-02942877, version 1


Sergej Scheck, Alexandre Niveau, Bruno Zanuttini. Knowledge Compilation for Action Languages. Journées Francophones sur la Planification, la Décision et l’Apprentissage pour la conduite de systèmes (JFPDA 2019), Jul 2020, Angers, France. ⟨hal-02942877⟩



Record views


Files downloads