Complexity of fuzzy answer set programming under Lukasiewicz semantics

Blondeel, Marjon, Schockaert, Steven ORCID: https://orcid.org/0000-0002-9256-2881, Vermeir, Dirk and De Cock, Martine 2014. Complexity of fuzzy answer set programming under Lukasiewicz semantics. International Journal of Approximate Reasoning 55 (9) , pp. 1971-2003. 10.1016/j.ijar.2013.10.011

Full text not available from this repository.

Abstract

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 Łukasiewicz 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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords:	Answer set programming; Łukasiewicz logic; Computational complexity
Publisher:	Elsevier
ISSN:	0888-613X
Last Modified:	27 Oct 2022 10:01
URI:	https://orca.cardiff.ac.uk/id/eprint/68586

Citation Data

Cited 9 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item