Propositional theories are strongly equivalent to logic programs

2007/01/16 by Pedro Cabalar, Cabalar, Pedro, Paolo Ferraris +1
Computer Science · #Advanced Algebra and Logic #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems

paper · pdf · doi:10.48550/arxiv.cs/0701095

openalex publication_date 2007/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents a property of propositional theories under the answer sets semantics (called Equilibrium Logic for this general syntax): any theory can always be reexpressed as a strongly equivalent disjunctive logic program, possibly with negation in the head. We provide two different proofs for this result: one involving a syntactic transformation, and one that constructs a program starting from the countermodels of the theory in the intermediate logic of here-and-there.

Related

• A General Framework for Equivalences in Answer-Set Programming by Countermodels in the Logic of Here-and-There
• Characterization of Strongly Equivalent Logic Programs in Intermediate Logics
• Alternative Characterizations for Strong Equivalence of Logic Programs
• Contextual hypotheses and semantics of logic programs
• Theories of truth for countable languages which conform to classical logic