• Simplifying logic programs und...

Result: Simplifying logic programs under uniform and strong equivalence

Title:
Simplifying logic programs under uniform and strong equivalence
Authors:
EITER, Thomas, FINK, Michael, TOMPITS, Hans, WOLTRAN, Stefan
Source:
LPNMR 2004 : logic programming and nonmonotonic reasoning (Fort Lauderdale FL, 6-8 January 2004)Lecture notes in computer science. :87-99
Publisher Information:
Berlin: Springer, 2004.
Publication Year:
2004
Physical Description:
print, 24 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Fonctions logiques, booléennes et de commutation, Logical, boolean and switching functions, Logiciel, Software, Généralités, General, Base connaissance, Knowledge base, Base conocimiento, Circonscription, Circumscription, Circonscripción, Complexité programme, Program complexity, Complejidad programa, Modèle logique, Logic model, Modelo lógico, Optimisation, Optimization, Optimización, Programmation logique, Logical programming, Programación lógica, Système expert, Expert system, Sistema experto, Sémantique, Semantics, Semántica, Transformation programme, Program transformation, Transformación programa
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institut für Informationssysteme 184/3, Technische Universität Wien, Favoritenstrasse 9-11, 1040 Vienna, Austria
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=15690796
Rights:
Copyright 2004 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.15690796
Database:
PASCAL Archive

Further Information

We consider the simplification of logic programs under the stable-model semantics, with respect to the notions of strong and uniform equivalence between logic programs, respectively. Both notions have recently been considered for nonmonotonic logic programs (the latter dates back to the 1980s, though) and provide semantic foundations for optimizing programs with input. Extending previous work, we investigate syntactic and semantic rules for program transformation, based on proper notions of consequence. We furthermore provide encodings of these notions in answer-set programming, and give characterizations of programs which are semantically equivalent to positive and Horn programs, respectively. Finally, we investigate the complexity of program simplification and determining semantical equivalence, showing that the problems range between coNP and ΠP2 complexity, and we present some tractable cases.