View in EDS

Strong equivalence of logic programs under the infinite-valued semantics

Saved in:
Bibliographic Details
Title: Strong equivalence of logic programs under the infinite-valued semantics
Authors: Nomikos, Christos1, Rondogiannis, Panos2 prondo@di.uoa.gr, Wadge, William W.3
Source: Information Processing Letters. May2009, Vol. 109 Issue 11, p576-581. 6p.
Subjects: Logic programming, Programming language semantics, Computer software, Propositional calculus, Infinite processes
Abstract: Abstract: We consider the notion of strong equivalence [V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526–541] of normal propositional logic programs under the infinite-valued semantics [P. Rondogiannis, W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 (2) (2005) 441–467] (which is a purely model-theoretic semantics that is compatible with the well-founded one). We demonstrate that two such programs are strongly equivalent under the infinite-valued semantics if and only if they are logically equivalent in the corresponding infinite-valued logic. In particular, we show that strong equivalence of normal propositional logic programs is decidable, and more specifically coNP-complete. Our results have a direct implication for the well-founded semantics since, as we demonstrate, if two programs are strongly equivalent under the infinite-valued semantics, then they are also strongly equivalent under the well-founded semantics. [Copyright &y& Elsevier]
Copyright of Information Processing Letters is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 37231482
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Strong equivalence of logic programs under the infinite-valued semantics
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Nomikos%2C+Christos%22">Nomikos, Christos</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Rondogiannis%2C+Panos%22">Rondogiannis, Panos</searchLink><relatesTo>2</relatesTo><i> prondo@di.uoa.gr</i><br /><searchLink fieldCode="AR" term="%22Wadge%2C+William+W%2E%22">Wadge, William W.</searchLink><relatesTo>3</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+Processing+Letters%22">Information Processing Letters</searchLink>. May2009, Vol. 109 Issue 11, p576-581. 6p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Logic+programming%22">Logic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Programming+language+semantics%22">Programming language semantics</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Propositional+calculus%22">Propositional calculus</searchLink><br /><searchLink fieldCode="DE" term="%22Infinite+processes%22">Infinite processes</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: We consider the notion of strong equivalence [V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526–541] of normal propositional logic programs under the infinite-valued semantics [P. Rondogiannis, W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 (2) (2005) 441–467] (which is a purely model-theoretic semantics that is compatible with the well-founded one). We demonstrate that two such programs are strongly equivalent under the infinite-valued semantics if and only if they are logically equivalent in the corresponding infinite-valued logic. In particular, we show that strong equivalence of normal propositional logic programs is decidable, and more specifically coNP-complete. Our results have a direct implication for the well-founded semantics since, as we demonstrate, if two programs are strongly equivalent under the infinite-valued semantics, then they are also strongly equivalent under the well-founded semantics. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information Processing Letters is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=37231482
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ipl.2009.02.002
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 6
        StartPage: 576
    Subjects:
      – SubjectFull: Logic programming
        Type: general
      – SubjectFull: Programming language semantics
        Type: general
      – SubjectFull: Computer software
        Type: general
      – SubjectFull: Propositional calculus
        Type: general
      – SubjectFull: Infinite processes
        Type: general
    Titles:
      – TitleFull: Strong equivalence of logic programs under the infinite-valued semantics
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Nomikos, Christos
      – PersonEntity:
          Name:
            NameFull: Rondogiannis, Panos
      – PersonEntity:
          Name:
            NameFull: Wadge, William W.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 16
              M: 05
              Text: May2009
              Type: published
              Y: 2009
          Identifiers:
            – Type: issn-print
              Value: 00200190
          Numbering:
            – Type: volume
              Value: 109
            – Type: issue
              Value: 11
          Titles:
            – TitleFull: Information Processing Letters
              Type: main
ResultId 1