Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Sufficient Condition for Strong Equivalence Under the Well-Founded Semantics

  • Conference paper
Logic Programming (ICLP 2005)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 3668))

Included in the following conference series:

Abstract

We consider the problem of strong equivalence [1] under the infinite-valued semantics [2] (which is a purely model-theoretic version of the well-founded semantics). We demonstrate that two programs are now strongly equivalent if and only if they are logically equivalent under the infinite-valued logic of [2]. In particular, we show that for propositional programs strong equivalence is decidable but coNP-complete. Our results have a direct practical 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.

This research is supported by EΠEAEK II under the task “ΠYΘAΓOPAΣ-II: ENIΣXYΣH EPEYNHTIKΩN OMAΔΩN ΣTA ΠANEΠIΣTHMIA”, Project title: Applications of Computational Logic to the Semantic Web, funded by the European Social Fund (75%) and the Greek Ministry of Education (25%).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Lifschitz, V., Pearce, D., Valverde, A.: Strongly Equivalent Logic Programs. ACM Transactions on Computational Logic 2(4), 526–541 (2001)

    Article  MathSciNet  Google Scholar 

  2. Rondogiannis, P., Wadge, W.W.: Minimum Model Semantics for Logic Programs with Negation-as-Failure. ACM Transactions on Computational Logic 6(2), 441–467 (2005)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Ioannina, P.O. Box 1186, 45 110, Ioannina, Greece

    Christos Nomikos

  2. Department of Informatics & Telecommunications, University of Athens, Panepistimiopolis, 157 84, Athens, Greece

    Panos Rondogiannis

  3. Department of Computer Science, University of Victoria, PO Box 3055, STN CSC, Victoria, BC, V8W 3P6, Canada

    William W. Wadge

Authors
  1. Christos Nomikos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Panos Rondogiannis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. William W. Wadge
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Scienze dell’Informazione, Università di Bologna, Italy

    Maurizio Gabbrielli

  2. Department of Computer Science, University of Texas at Dallas, 75080, Richardson, TX

    Gopal Gupta

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nomikos, C., Rondogiannis, P., Wadge, W.W. (2005). A Sufficient Condition for Strong Equivalence Under the Well-Founded Semantics. In: Gabbrielli, M., Gupta, G. (eds) Logic Programming. ICLP 2005. Lecture Notes in Computer Science, vol 3668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11562931_35

Download citation

  • DOI: https://doi.org/10.1007/11562931_35

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-29208-1

  • Online ISBN: 978-3-540-31947-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation