Graph Theoretical Characterization and Computation of Answer Sets
Abstract
We give a graph theoretical characterization of answer sets of normal logic programs. We show that there is a one-to-one correspondence between answer sets and a special, non-standard graph coloring of so-called block graphs of logic programs. This leads us to an alternative implementation paradigm to compute answer sets, by computing non-standard graph colorings. Our approach is rule-based and not atom-based like most of the currently known methods. We present an implementation for computing answer sets which works on polynomial space. 1
Cite
Text
Linke. "Graph Theoretical Characterization and Computation of Answer Sets." International Joint Conference on Artificial Intelligence, 2001.Markdown
[Linke. "Graph Theoretical Characterization and Computation of Answer Sets." International Joint Conference on Artificial Intelligence, 2001.](https://mlanthology.org/ijcai/2001/linke2001ijcai-graph/)BibTeX
@inproceedings{linke2001ijcai-graph,
title = {{Graph Theoretical Characterization and Computation of Answer Sets}},
author = {Linke, Thomas},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2001},
pages = {641-648},
url = {https://mlanthology.org/ijcai/2001/linke2001ijcai-graph/}
}