Preferred arguments are harder to compute than stable extensions
SourceIJCAI International Joint Conference on Artificial Intelligence
16th International Joint Conference on Artificial Intelligence, IJCAI 1999
Google Scholar check
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
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 ...
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, ...
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 ...