Computational properties of argument systems satisfying graph-theoretic constraints

DOI10.1016/j.artint.2007.03.006zbMath1168.68565OpenAlexW2100875224MaRDI QIDQ1028949

Paul E. Dunne

Publication date: 9 July 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2007.03.006

zbMATH Keywords

computational complexityargumentation frameworkscomputational properties of argumentation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Logic in artificial intelligence (68T27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (41)

Backdoors to Satisfaction ⋮ Looking-ahead in backtracking algorithms for abstract argumentation ⋮ On rejected arguments and implicit conflicts: the hidden power of argumentation semantics ⋮ Toward incremental computation of argumentation semantics: a decomposition-based approach ⋮ Weighted argumentation for analysis of discussions in Twitter ⋮ Equivalence in logic-based argumentation ⋮ Lattice point of view for argumentation framework ⋮ On checking skeptical and ideal admissibility in abstract argumentation frameworks ⋮ The complexity landscape of claim-augmented argumentation frameworks ⋮ On the preferred extensions of argumentation frameworks: bijections with naive sets ⋮ Query complexity of tournament solutions ⋮ Algorithms and complexity results for persuasive argumentation ⋮ Dynamics of argumentation systems: a division-based method ⋮ A QBF-based formalization of abstract argumentation semantics ⋮ Complexity of semi-stable and stage semantics in argumentation frameworks ⋮ Minimal retentive sets in tournaments ⋮ Approximating agreements in formal argumentation dialogues1 ⋮ Complexity-sensitive decision procedures for abstract argumentation ⋮ Algorithms for decision problems in argument systems under preferred semantics ⋮ Structural Analysis of Extension-Based Argumentation Semantics with Joint Acceptability ⋮ New width parameters for SAT and \#SAT ⋮ Acceptance in incomplete argumentation frameworks ⋮ Uses and computation of imprecise probabilities from statistical data and expert arguments ⋮ Argumentation frameworks as constraint satisfaction problems ⋮ A computational analysis of the tournament equilibrium set ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Augmenting tractable fragments of abstract argumentation ⋮ Weighted argument systems: basic definitions, algorithms, and complexity results ⋮ On the resolution-based family of abstract argumentation semantics and its grounded instance ⋮ Meta-argumentation modelling. I: Methodology and techniques ⋮ Initial sets in abstract argumentation frameworks ⋮ Valid attacks in argumentation frameworks with recursive attacks ⋮ Graph-classes of argumentation frameworks with collective attacks ⋮ A new approach for preference-based argumentation frameworks ⋮ A distributed argumentation algorithm for mining consistent opinions in weighted Twitter discussions ⋮ A general notion of equivalence for abstract argumentation ⋮ The computational complexity of ideal semantics ⋮ Complexity of abstract argumentation under a claim-centric view ⋮ Methods for solving reasoning problems in abstract argumentation -- a survey ⋮ Backdoors to tractable answer set programming ⋮ Indepth combinatorial analysis of admissible sets for abstract argumentation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph theoretical structures in logic programs and default theories
• Two party immediate response disputes: Properties and efficiency
• Audiences in argumentation frameworks
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• A partial k-arboretum of graphs with bounded treewidth
• An abstract, argumentation-theoretic approach to default reasoning
• A reasoning model based on the production of acceptable arguments
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Coherence in finite argument systems.
• On the computational complexity of assumption-based argumentation for default reasoning.
• On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games
• Dialectic proof procedures for assumption-based, admissible argumentation
• SCC-recursiveness: a general schema for argumentation semantics
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A Separator Theorem for Planar Graphs
• Planar Crossovers
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The relative efficiency of propositional proof systems
• Persuasion in Practical Argument Using Value-based Argumentation Frameworks
• Fixed-Parameter Tractability and Completeness I: Basic Results
• The Complexity of Propositional Proofs
• Theory and Applications of Satisfiability Testing
• Logics in Artificial Intelligence
• Symbolic and Quantitative Approaches to Reasoning with Uncertainty
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Symbolic and Quantitative Approaches to Reasoning with Uncertainty

This page was built for publication: Computational properties of argument systems satisfying graph-theoretic constraints