Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11019
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Nomikos, C. | en |
dc.contributor.author | Rondogiannis, P. | en |
dc.contributor.author | Wadge, W. W. | en |
dc.date.accessioned | 2015-11-24T17:02:09Z | - |
dc.date.available | 2015-11-24T17:02:09Z | - |
dc.identifier.issn | 0020-0190 | - |
dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11019 | - |
dc.rights | Default Licence | - |
dc.subject | formal semantics | en |
dc.subject | negation in logic programming | en |
dc.subject | strong equivalence | en |
dc.title | Strong equivalence of logic programs under the infinite-valued semantics | en |
heal.type | journalArticle | - |
heal.type.en | Journal article | en |
heal.type.el | Άρθρο Περιοδικού | el |
heal.identifier.primary | DOI 10.1016/j.ipl.2009.02.002 | - |
heal.language | en | - |
heal.access | campus | - |
heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
heal.publicationDate | 2009 | - |
heal.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. (C) 2009 Elsevier B.V. All rights reserved. | en |
heal.journalName | Information Processing Letters | en |
heal.journalType | peer reviewed | - |
heal.fullTextAvailability | TRUE | - |
Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Nomikos-2009-Strong equivalence o.pdf | 163.08 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License