Knowledge compilation for nondeterministic action languages - GREYC mad Access content directly
Theses Year : 2022

Compilation de connaissances pour les langages d’actions non déterministes

Knowledge compilation for nondeterministic action languages

Abstract

In this thesis we study formal languages for representing nondeterministic actions from the perspectiveof Knowledge Compilation. We define a formal framework to capture essential features of languageslike the “Planning Domain Definition Language” PDDL in a propositional setting, and present a numberof languages which are either abstract nondeterministic versions of action languages from the literatureor their modifications obtained by extending or restricting the sets of possible action descriptions. Exten-sions are obtained by allowing additional connectives in the grammar, whereas restrictions are obtainedby either allowing only expressions of a certain structure or removing constructs from the grammar. Wecompare those languages with respect to three criteria: complexity of answering queries, possibility ofperforming transformations without a superpolynomial explosion in size, and relative succinctness. Wegive a complete picture for complexities of all queries for all languages, and an almost complete picturefor transformations and queries for languages which are not very rich but still fully expressive. Ourresults agree with the intuition that there is a tradeoff between the succinctness and the complexity ofqueries. We still identify several cases where it might be useful to prefer one representation over another.
Dans cette thèse, nous étudions les langages formels pour représenter des actions non déterministes dupoint de vue de la compilation de connaissances. Nous donnons un cadre formel pour capturer les carac-téristiques essentielles de langages d’actions comme le « Planning Domain Definition Language » PDDLdans le cadre propositionnel, et présentons des langages qui sont des versions abstraites non déterministesdes langages d’action de la littérature, ou leurs modifications obtenues en étendant ou en restreignant lesensembles de descriptions d’actions possibles. Les extensions sont obtenues en ajoutant des connecteurssupplémentaires à la grammaire, tandis que les restrictions sont obtenues en n’autorisant que les des-criptions d’actions d’une certaine structure ou en supprimant des connecteurs de la grammaire. Nouscomparons ces langages par rapport à trois critères : la complexité de répondre aux requêtes, la possi-bilité d’effectuer des transformations sans explosion en taille superpolynomiale, et la concision. Nousdonnons une image complète pour les complexités de toutes les requêtes pour tous les langages, et uneimage presque complète pour les transformations et les requêtes pour les langages qui ne sont pas trèsriches mais toujours capables d’exprimer toutes les actions. Nos résultats concordent avec l’intuition quegénéralement il existe un compromis entre la concision et la complexité des requêtes. Nous identifionstout de même plusieurs cas où il pourrait être utile de préférer une représentation plutôt qu’une autre.
Fichier principal
Vignette du fichier
sygal_fusion_42227-scheck-sergej_6437d5c69fe3b.pdf (846.48 Ko) Télécharger le fichier
Origin : Version validated by the jury (STAR)

Dates and versions

tel-04067436 , version 1 (13-04-2023)

Identifiers

  • HAL Id : tel-04067436 , version 1

Cite

Sergej Scheck. Knowledge compilation for nondeterministic action languages. Informatique et langage [cs.CL]. Normandie Université, 2022. Français. ⟨NNT : 2022NORMC265⟩. ⟨tel-04067436⟩
39 View
12 Download

Share

Gmail Facebook X LinkedIn More