A new exact algorithm for computing answer sets of logic programs is presented and analyzed. The algorithm takes a logic program in Kernel normal form as an input and computes its answer sets by reducing the problem to a suitable version of graph colorability. Even though worst-case complexity is exponential, thanks to a straightforward formulation we can prove that the algorithm works in time O*(1.6181n), which is asymptotically better than the trivial bound O*(2n) of the brute force algorithms. We argue that this new algorithm represents a significant progress in terms of worst-case time complexity over traditional branch-and-bound algorithms.
A New Algorithm for Answer Set Computation / Giuliano Grossi, Massimo Marchi - In: Answer Set Programming, Advances in Theory and Implementation : Proceedings of the 3rd Intl. ASP'05 Workshop : Bath, UK, September 27-29, 2005. / Marina De Vos, Alessandro Provetti. - Aachen : CEUR WS, 2005. - pp. 155-162 (( Intervento presentato al 3. convegno International ASP Workshop tenutosi a Bath, UK nel 2005.
A New Algorithm for Answer Set Computation
G. Grossi;M. Marchi
2005
Abstract
A new exact algorithm for computing answer sets of logic programs is presented and analyzed. The algorithm takes a logic program in Kernel normal form as an input and computes its answer sets by reducing the problem to a suitable version of graph colorability. Even though worst-case complexity is exponential, thanks to a straightforward formulation we can prove that the algorithm works in time O*(1.6181n), which is asymptotically better than the trivial bound O*(2n) of the brute force algorithms. We argue that this new algorithm represents a significant progress in terms of worst-case time complexity over traditional branch-and-bound algorithms.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
