Preferred arguments are harder to compute than stable extensions
Date
1999Source
IJCAI International Joint Conference on Artificial Intelligence16th International Joint Conference on Artificial Intelligence, IJCAI 1999
Volume
1Pages
36-41Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Based on an abstract framework for nonmonotonic reasoning, Bondarenko et at. have extended the logic programming semantics of admissible and preferred arguments to other nonmonotonic formalisms such as circumscription, autoepisternic logic and default logic. Although the new semantics have been tacitly assumed to mitigate the computational problems of nonmonotonic reasoning under the standard semantics of stable extensions, it seems questionable whether they improve the worst-case behaviour. As a matter of fact, we show that credulous reasoning under the new semantics in propositional logic programming and prepositional default logic has the same computational complexity as under the standard semantics. Furthermore, sceptical reasoning under the admissibility semantics is easier - since it is trivialised to monotonic reasoning. Finally, sceptical reasoning under the preferability semantics is harder than under the standard semantics.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
Argumentation Logic
Kakas, Antonis C.; Toni, F.; Mancarella, P. (2014)We propose a novel logic-based argumentation framework, called Argumentation Logic (AL), built upon a restriction of classical Propositional Logic (PL) as its underlying logic. This allows us to control the application of ...
-
Conference Object
Modelling inhibition in metabolic pathways through abduction and induction
Tamaddoni-Nezhad, A.; Kakas, Antonis C.; Muggleton, S.; Pazos, F. (2004)In this paper, we study how a logical form of scientific modelling that integrates together abduction and induction can be used to understand the functional class of unknown enzymes or inhibitors. We show how we can model, ...
-
Article
Classical methods in nonmonotonic reasoning
Dimopoulos, Yannis (1994)In this paper we present and compare some classical problem solving methods for computing the stable models of a general propositional logic program. In particular linear programming, propositional satisfiability, constraint ...