In recent years a number of positive (i.e. tractability and decidability) results have been found concerning the computational complexity of Description Logics (DLs) Unfortunately, also negative results have appeared which show that some DLs (e.g NIKL and KL-ONE) are undecidable. This work contributes to this latter literature by showing an undecidability result for another DL (called MIRTL) which had not been previously studied from the standpoint of computational complexity and which is not directly related to the ones already shown undecidable.

Logical and computational properties of the description logic MIRTL

Meghini C;Sebastiani F;Straccia U
1995

Abstract

In recent years a number of positive (i.e. tractability and decidability) results have been found concerning the computational complexity of Description Logics (DLs) Unfortunately, also negative results have appeared which show that some DLs (e.g NIKL and KL-ONE) are undecidable. This work contributes to this latter literature by showing an undecidability result for another DL (called MIRTL) which had not been previously studied from the standpoint of computational complexity and which is not directly related to the ones already shown undecidable.
1995
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
Description logic
Information Storage and Retrieval
File in questo prodotto:
File Dimensione Formato  
prod_227008-doc_144317.pdf

solo utenti autorizzati

Descrizione: Logical and computational properties of the description logic
Tipologia: Versione Editoriale (PDF)
Dimensione 2.15 MB
Formato Adobe PDF
2.15 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/121212
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact