Graph Theoretical Characterization and Computation of Answer Sets

Linke, Thomas

Graph Theoretical Characterization and Computation of Answer Sets

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 641-647.

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.

Thomas Linke. 2001. Graph Theoretical Characterization and Computation of Answer Sets. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01. IJCAI, 641–647. https://ijcai.org/proceedings/2001/89

@inproceedings{ijcai2001p89,
  title     = {Graph Theoretical Characterization and Computation of Answer Sets},
  author    = {Linke, Thomas},
  booktitle = {Proceedings of the Seventeenth International Joint Conference on
               Artificial Intelligence, {IJCAI-01}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {641--647},
  year      = {2001},
  url       = {https://ijcai.org/proceedings/2001/89},
}

TY  - CPAPER
TI  - Graph Theoretical Characterization and Computation of Answer Sets
AU  - Linke, Thomas
T2  - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2001
SP  - 641
EP  - 647
UR  - https://ijcai.org/proceedings/2001/89
ER  -