On equivalence of infinitary formulas under the stable model semantics

DOI10.1017/S1471068414000088MaRDI QIDQ4592970zbMATHOpenAlexFDO

Authors Amelia Harrison, Vladimir Lifschitz, Mirosław Truszczyński

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.6689

zbMATH Keywords

answer set programmingintuitionistic logicstrong equivalencesemantics of aggregates

Mathematics Subject Classification ID

Logic programming (68N17) Logic in computer science (03B70) Semantics in the theory of computing (68Q55)

Abstract: Propositional formulas that are equivalent in intuitionistic logic, or in its extension known as the logic of here-and-there, have the same stable models. We extend this theorem to propositional formulas with infinitely long conjunctions and disjunctions and show how to apply this generalization to proving properties of aggregates in answer set programming. To appear in Theory and Practice of Logic Programming (TPLP).

Recommendations

• On Equivalent Transformations of Infinitary Formulas under the Stable Model Semantics
• Stable models for infinitary formulas with extensional atoms
• scientific article; zbMATH DE number 1302492
• Equivalence for the \(G_3^\prime\)-stable models semantics
• Stable models of formulas with generalized quantifiers (preliminary report)
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• Infinitary formulas preserved under unions of models
• scientific article; zbMATH DE number 1163986
• Stable formulas in intuitionistic logic
• Model theory for infinite quantifier languages

Cites work

• scientific article; zbMATH DE number 3206304 (Why is no real title available?)
• scientific article; zbMATH DE number 3250542 (Why is no real title available?)
• Connecting first-order ASP and the logic FO(ID) through reducts
• Logic Programming and Nonmonotonic Reasoning
• On Equivalent Transformations of Infinitary Formulas under the Stable Model Semantics
• Strongly equivalent logic programs
• The sentential calculus with infinitely long expressions

Cited in

(13)

• An abstract, logical approach to characterizing strong equivalence in non-monotonic knowledge representation formalisms
• Infinitary Equilibrium Logic and Strong Equivalence
• Some remarks on equivalence in infinitary and stationary logic
• On Equivalent Transformations of Infinitary Formulas under the Stable Model Semantics
• Safe Formulas in the General Theory of Stable Models (Preliminary Report)
• Forgetting auxiliary atoms in forks
• Iteratively-supported formulas and strongly supported models for Kleene answer set programs (extended abstract)
• Gelfond-Zhang aggregates as propositional formulas
• Proving infinitary formulas
• Infinitary definitions of equivalence relations in models of PA
• Erratum to: ``Reasoning with infinite stable models
• Stable models for infinitary formulas with extensional atoms
• Infinitary equilibrium logic and strongly equivalent logic programs

This page was built for publication: On equivalence of infinitary formulas under the stable model semantics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592970)