Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Program correspondence under the answer-set semantics: The non-ground case
Institut für Informationssysteme, Arbeitsbereich Wissensbasierte Systeme 184/3, Technische Universität Wien, Vienna, Austria.ORCID iD: 0000-0002-9902-7662
Institut für Informationssysteme, Arbeitsbereich Wissensbasierte Systeme 184/3, Technische Universität Wien, Vienna, Austria.
2008 (English)In: Logic Programming: 24th International Conference, ICLP 2008 Udine, Italy, December 9-13 2008, Proceedings / [ed] M. Garcia de la Banda, & E. Pontelli, Springer, 2008, p. 591-605Conference paper, Published paper (Refereed)
Abstract [en]

The study of various notions of equivalence between logic programs in the area of answer-set programming (ASP) gained increasing interest in recent years. The main reason for this undertaking is that ordinary equivalence between answer-set programs fails to yield a replacement property similar to the one of classical logic. Although many refined program correspondence notions have been introduced in the ASP literature so far, most of these notions were studied for propositional programs only, which limits their practical usability as concrete programming applications require the use of variables. In this paper, we address this issue and introduce a general framework for specifying parameterised notions of program equivalence for non-ground disjunctive logic programs under the answer-set semantics. Our framework is a generalisation of a similar one defined previously for the propositional case and allows the specification of several equivalence notions extending well-known ones studied for propositional programs. We provide semantic characterisations for instances of our framework generalising uniform equivalence, and we study decidability and complexity aspects. Furthermore, we consider axiomatisations of such correspondence problems by means of polynomial translations into second-order logic. 

Place, publisher, year, edition, pages
Springer, 2008. p. 591-605
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 5366
Keywords [en]
Computability and decidability, Computer programming, Computer systems programming, Information theory, Programming theory, Semantics, Knowledge representation, Logic programming, Correspondence problems, Equivalence notions, General framework, Logic programs, Program equivalence, Set programming, Set semantics, Application programs, Answer set programming, Answer set semantics, Disjunctive logic programs, Polynomial translation, Second-order logic
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:hj:diva-63587DOI: 10.1007/978-3-540-89982-2_49Scopus ID: 2-s2.0-58549111116ISBN: 3540899812 (print)ISBN: 9783540899815 (print)OAI: oai:DiVA.org:hj-63587DiVA, id: diva2:1838163
Conference
24th International Conference, ICLP 2008 Udine, Italy, December 9-13, 2008
Available from: 2024-02-15 Created: 2024-02-15 Last updated: 2024-02-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Oetsch, Johannes

Search in DiVA

By author/editor
Oetsch, Johannes
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 5 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf