[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Some Complexity Results on Fuzzy Description Logics

  • Conference paper
Fuzzy Logic and Applications (WILF 2003)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2955))

Included in the following conference series:

  • 635 Accesses

Abstract

We present and discuss some novel and somewhat surprising complexity results for a basic but significant fuzzy description logic (DL) which extends the classical \(\mathcal{ALC}\) language. In particular we show that checking the consistency of a concept or a KB in fuzzy DLs has a complexity which jumps from linear-time to EXPTIME-complete, while the subsumption problem is always (at least) as hard as in crisp DLs.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, implementation and applications, Cambridge (2003)

    Google Scholar 

  2. Butnariu, D., Klement, E.P., Zafrany, S.: On triangular norm-based propositional fuzzy logics. Fuzzy Sets and Systems 69, 241–255 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Navara, M.: Satisfiability in fuzzy logics. Neural Networks World 10(5), 845–858 (2000)

    Google Scholar 

  4. Straccia, U.: Reasoning within fuzzy description logics. Journal of Artificial Intelligence Research 14, 137–166 (2001)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Scienze Fisiche — Sezione di Informatica, Complesso Universitario di Monte Sant’Angelo, Università di Napoli “Federico II”, Via Cinthia, Napoli, Italy

    Piero A. Bonatti

  2. Dipartimento di Tecnologie dell’Informazione, Università degli Studi di Milano, Via Bramante 65, I-26013, Crema (CR), Italy

    Andrea G. B. Tettamanzi

Authors
  1. Piero A. Bonatti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrea G. B. Tettamanzi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Stanford University, Department of Statistics, Stanford, CA, USA

    Vito Di Gesú

  2. Department of Computer and Information Sciences, University of Genova, and CNISM, Via Dodecaneso 35, I-16146, Genova, Italy

    Francesco Masulli

  3. Centro Direzionale, DSA, University of Naples Parthenope, Isola C/4, 80143, Naples, Italy

    Alfredo Petrosino

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bonatti, P.A., Tettamanzi, A.G.B. (2006). Some Complexity Results on Fuzzy Description Logics. In: Di Gesú, V., Masulli, F., Petrosino, A. (eds) Fuzzy Logic and Applications. WILF 2003. Lecture Notes in Computer Science(), vol 2955. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10983652_3

Download citation

  • DOI: https://doi.org/10.1007/10983652_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-31019-8

  • Online ISBN: 978-3-540-32683-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation