Complexité de l’argumentation dans le cadredu treillis de Post

• Dans beaucoup de formalisations logiques de l’argumentation un ar-gument est présenté comme une paire (Φ,α), où le support Φ est un sous-ensemble consistant minimal d’une base de connaissances qui implique l’affirmationα. Dans la plupart des scénarii les arguments sont donnés dans le langage completde la logique propositionnelle. Dans un tel contexte le raisonnement est une tâche algorithmique très difficile. Par exemple, décider s’il existe un support pour une affirmation donnée est Σp2-complet. Afin de comprendre ce qui est à la source dela difficulté de ce problème (et d’identifier des fragments résolubles efficacement) nous nous intéressons aux arguments donnés sous la forme de formules propositionnelles dont les connecteurs logiques font partie d’un ensemble de fonctions booléennes donné. Nous considérons quatre problèmes de décision : existe-t-il unsupport pour un argument ? un argument est-il valide ? une formule donnée est-elle pertinente (resp. superflue) dans les prémisses d’un argument ? Nous classifions la complexité de ces problèmes selon tous les ensembles possibles deconnecteurs autorisés.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)