Complexity of fuzzy answer set programming under Lukasiewicz semantics

Marjon Blondeel, Steven Schockaert, Dirk Vermeir, Martine De Cock

Onderzoeksoutput: Articlepeer review

10 Citaten (Scopus)


Fuzzy answer set programming (FASP) is a generalization of answer set programming (ASP) in which propositions are allowed to be graded. Little is known about the computational complexity of FASP and almost no techniques are available to compute the answer sets of a
FASP program. In this paper, we analyze the computational complexity of FASP under Lukasiewicz semantics. In particular we show
that the complexity of the main reasoning tasks is located at the first level of the polynomial hierarchy, even for disjunctive FASP programs for which reasoning is classically located at the second level. Moreover, we show a reduction from reasoning with such FASP programs to bilevel linear programming, thus opening the door to practical applications. For definite FASP programs we can show P-membership. Surprisingly, when allowing disjunctions to occur in the body of rules -- a syntactic generalization which does not affect the expressivity of ASP in the classical case -- the picture changes drastically. In particular, reasoning tasks are then located at the second level of the polynomial hierarchy, while for simple FASP programs, we can only show that the unique answer set can be found in pseudo-polynomial time.Moreover, the connection to an existing open problem about integer equations suggests that the problem of fully characterizing the complexity of FASP in this more general setting is not likely to have an easy solution.
Originele taal-2English
Pagina's (van-tot)1971-2003
Aantal pagina's33
TijdschriftInternational Journal of Approximate Reasoning
Nummer van het tijdschrift9
StatusPublished - 2014


Duik in de onderzoeksthema's van 'Complexity of fuzzy answer set programming under Lukasiewicz semantics'. Samen vormen ze een unieke vingerafdruk.

Citeer dit