SpringerLink
Log in

A Tableau Method with Optimal Complexity for Deciding the Description Logic SHIQ

  • Conference paper
Advanced Computational Methods for Knowledge Engineering

Part of the book series: Studies in Computational Intelligence ((SCI,volume 479))

  • 1722 Accesses

Abstract

We present the first tableau method with an ExpTime (optimal) complexity for checking satisfiability of a knowledge base in the description logic \(\mathcal{SHIQ}\). The complexity is measured using binary representation for numbers. Our method is based on global state caching and integer linear feasibility checking.

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
EUR 32.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
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 160.49
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 210.99
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
EUR 210.99
Price includes VAT (France)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Farsiniamarj, N.: Combining integer programming and tableau-based reasoning: a hybrid calculus for the description logic SHQ. Master’s thesis, Concordia University (2008)

    Google Scholar 

  2. Goré, R., Widmann, F.: Sound global state caching for ALC with inverse roles. In: Giese, M., Waaler, A. (eds.) TABLEAUX 2009. LNCS, vol. 5607, pp. 205–219. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  3. Horrocks, I., Sattler, U., Tobies, S.: Reasoning with individuals for the description logic SHIQ. In: McAllester, D. (ed.) CADE-17. LNCS, vol. 1831, pp. 482–496. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  4. Nguyen, L.A.: An efficient tableau prover using global caching for the description logic \(\mathcal{ALC}\). Fundamenta Informaticae 93(1-3), 273–288 (2009)

    MathSciNet  MATH  Google Scholar 

  5. Nguyen, L.A.: A cut-free ExpTime tableau decision procedure for the description logic SHI. In: Jędrzejowicz, P., Nguyen, N.T., Hoang, K. (eds.) ICCCI 2011, Part I. LNCS, vol. 6922, pp. 572–581. Springer, Heidelberg (2011), http://arxiv.org/abs/1106.2305

    Chapter  Google Scholar 

  6. Nguyen, L.A.: Exptime tableaux for the description logic SHIQ based on global state caching and integer linear feasibility checking. ar**v:1205.5838 (2012)

    Google Scholar 

  7. Tobies, S.: Complexity results and practical algorithms for logics in knowledge representation. PhD thesis, RWTH-Aachen (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Informatics, University of Warsaw, Banacha 2, 02-097, Warsaw, Poland

    Linh Anh Nguyen

  2. Faculty of Information Technology, College of Technology, Vietnam National University, 144 Xuan Thuy, Hanoi, Vietnam

    Linh Anh Nguyen

Authors
  1. Linh Anh Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Linh Anh Nguyen .

Editor information

Editors and Affiliations

  1. , Division of Knowledge Management Systems, Wroclaw University of Technology, Str. Wyb. Wyspianskiego 27, Wroclaw, 50-370, Poland

    Ngoc Thanh Nguyen

  2. and Economics, Department of Telecommunications, Budapest University of Technology, Pazmany Peter setany 1/D, Budapest, 1111, Hungary

    Tien van Do

  3. LITA - UFR MIM, Université de Lorraine – Metz, Ile du Saulcy, Metz Cedex 01, 57045, France

    Hoai An le Thi

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer International Publishing Switzerland

About this paper

Cite this paper

Nguyen, L.A. (2013). A Tableau Method with Optimal Complexity for Deciding the Description Logic SHIQ. In: Nguyen, N., van Do, T., le Thi, H. (eds) Advanced Computational Methods for Knowledge Engineering. Studies in Computational Intelligence, vol 479. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-00293-4_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-00293-4_25

  • Publisher Name: Springer, Heidelberg

  • Print ISBN: 978-3-319-00292-7

  • Online ISBN: 978-3-319-00293-4

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation