Lógica de descripción

Las lógicas de descripción, también llamadas lógicas descriptivas (DL por description logics) son una familia de lenguajes de representación del conocimiento que pueden ser usados para representar conocimiento terminológico de un dominio de aplicación de una forma estructurada y formalmente bien comprendida. El nombre lógica de descripción se refiere, por un lado, a descripciones de conceptos usadas para describir un dominio y, por otro lado, a la semántica que establece una equivalencia entre las fórmulas de lógicas de descripción y expresiones en lógica de predicados de primer orden. DL se diseñó como una extensión de frames (marcos) y redes semánticas, los cuales no estaban equipados con semántica basada en la lógica. A diferencia de los demás sistemas de representación (redes semánticas y frames), estas lógicas están dotadas con una semántica formal basada en lógica y tienen características muy importantes como son:

• Un formalismo descriptivo: conceptos, roles, individuos y constructores.
• Un formalismo terminológico: axiomas terminológicos que introducen descripciones complejas y propiedades de la terminología descriptiva.
• Un formalismo asertivo: que introduce propiedades de individuos.
• Son capaces de inferir nuevo conocimiento a partir de conocimiento dado; tienen por tanto, algoritmos de razonamiento que son decidibles.

Los elementos centrales del alfabeto del lenguaje de las lógicas de descripción son:

• Nombres de concepto (concept name): asignan un nombre a un grupo de objetos.
• Nombres de rol (role name): asigna un nombre a una relación entre objetos.
• Nombres de individuos (u objetos): los individuos son instancias de los conceptos y también se pueden relacionar por medio de un rol.
• Constructores (constructor): relaciona nombres de conceptos y nombres de roles, y también crea conceptos complejos a partir de los atómicos (complex concepts).
• Definiciones de conceptos complejos: usa los símbolos ${\displaystyle \doteq }$ y ${\displaystyle \sqsubseteq }$ para declarar conjunto de igualdades y conjuntos de inclusiones.

El nombre de lógica de descripción es de los años 1980s. Antes de esto se llamaba (cronológicamente): sistemas terminológicos, y lenguajes de conceptos. Las lógicas de descripción de hoy en día se han convertido en una piedra fundamental de la web semántica para su uso en el diseño de ontologías.

El primer sistema basado en DL fue KL-ONE (por Brachman and Schmolze, 1985). Después vinieron algunos otros sistemas de DL. Están LOOM (1987), BACK (1988), KRIS (1991), CLASSIC (1991), FaCT (1998), RACER (2001), CEL (2005), KAON 2 (2005) y JCEL (2010).

El desarrollo de OIL fue inspirado en DL.

Modelando con Lógicas de Descripción

En DLs, existe un distinción entre la llamada TBox (caja terminológica) y la ABox (caja de aserciones). En general, la TBox contiene sentencias describiendo conceptos jerárquicos ( i.e., relaciones entre conceptos) mientras la ABox contiene sentencias "ground" indicando a donde pertenecen los individuos en la jerarquía (i.e., relaciones entre individuos y conceptos). Por ejemplo, la frase:

(1) Cada empleado es una persona

pertenece a la TBox, mientras que la frase:

(2) Bob es un empleado

pertenece a la ABox. Nótese que la distinción entre TBox y ABox no es significante en el mismo sentido que en la lógica de primer orden (la cual subsume la mayoría de las DL). Las dos "clases" de sentencias se tratan de igual forma. Cuando se traduce a lógica de primer orden, un axioma de subsumición como (1) es simplemente un condicional restringido a predicados unarios (conceptos) donde sólo aparecen variables. Una sentencia de esta forma no tiene un tratamiento distinto de las sentencias donde sólo aparecen constantes (valores "ground ") como en (2).

Entonces, ¿por qué hacer esta distinción? La principal razón es que esta separación puede ser útil para describir y formular procedimientos de decisión para varias DL. Por ejemplo, un razonador podría procesar la TBox y la ABox por separado. Ciertos problemas claves de inferencia están ligados a una pero no a la otra ('clasificación' está relacionado con la TBox, 'chequeo de instancia' a la ABox). Además la complejidad de la TBox puede afectar considerablemente el rendimiento de un procedimiento de decisión para cierta DL, independientemente de la ABox. Así resulta útil una forma de hablar de una parte específica de una base de conocimiento (KB). Otro motivo de esta distinción es que tenga sentido desde el punto de vista del que modela la base de conocimiento. Es conveniente poder distinguir entre los conceptos en el mundo (axiomas de clase en la TBox) y las manifestaciones particulares de esos conceptos (aserciones de instancia en la ABox)

Diferencias con OWL

Terminología

Un concepto en la jerga de DL se refiere a una clase en OWL. Un rol en la jerga de DL es una propiedad en OWL.

Nombres

OWL no necesita la Suposición de Nombres Únicos (UNA por Unique Name Assumption).

Razonadores para Lógicas de Descripción

A continuación se detallan los más populares razonadores para manejarse con OWL y con DL:

• CEL es un razonador basado en LISP, gratuito para uso no comercial.
• Cerebra Engine el 19 de abril de 2006 en Wayback Machine. es un razonador comercial basado en C++.
• FaCT++ es un razonador basado en C++, gratuito open-source.
• KAON2 es un razonador basado en Java, gratuito para uso no comercial.
• MSPASS es un razonador basado en C, gratuito y open-source.
• es un razonador basado en Java, gratuito open-source.
• RacerPro es un razonador basado en LISP comercial, pero con trials gratuitos y licencias de investigación.

Otras herramientas relacionadas con DLs incluyen los siguientes:

• Protégé es un editor de ontologías y frameworks de bases de conocimiento, gratuito open-source. Puede usar razonadores de DL que ofrecen una interfaz DIG para chequeos de consistencia.

La lógica ${\displaystyle {\mathcal {ALC}}}$

Las lógicas ${\displaystyle {\mathcal {AL}}}$  (AL por attributive language) constituyen una familia de lógica populares. Cada una agrega letras a su nombre para indicar su poder expresivo. Una lógica popular es la lógica ${\displaystyle {\mathcal {ALC}}}$ , la cual utiliza una notación estándar, comúnmente conocida como sintaxis alemana debido a la nacionalidad de sus creadores, que se ha adoptado ampliamente para la discusión teórica sobre DL. Esta notación usa los símbolos:

• “${\displaystyle \sqcap }$ ” y “${\displaystyle \sqcup }$ ” para operadores de conjunción y disyunción, reflejando su interpretación del modelo teórico como el conjunto de intersección y unión.
• “${\displaystyle \forall }$ ” y “${\displaystyle \exists }$ ” cuantificadores lógicos estándar, símbolos para restricción de valor y restricción existencial.
• “${\displaystyle \lnot }$ ” para el complemento.

Variedad de otros símbolos también pueden usarse para representar operadores adicionales, que serán descritos más adelante.

Los símbolos de relación “${\displaystyle \doteq }$ ” y “${\displaystyle \sqsubseteq }$ ” se usan en axiomas y reflejan su interpretación en el modelo teórico como conjunto de igualdad y conjunto de inclusión.

Sintaxis de ${\displaystyle {\mathcal {ALC}}}$ 

La sintaxis de estas lógicas soportan la descripción lógica de conceptos, roles (relaciones) e individuos, donde los conceptos y roles pueden ser combinados, usando una variedad de operadores, para formar expresiones más complejas. Los operadores soportados por las lógicas de descripción, normalmente incluyen algunas o todas las conectivas lógicas estándares juntamente con uno o ambos operadores relacionales (cuantificadores universales y existenciales llamados restricciones de valor y restricciones existenciales).

Formalmente una terminología en ${\displaystyle {\mathcal {ALC}}}$  está definida por la siguiente formación de reglas:

• Los axiomas son de la forma:

${\displaystyle C\doteq D\mid C\sqsubseteq D}$ 

donde C y D son las expresiones de concepto.

• La expresiones de concepto de la forma:

${\displaystyle CN\mid \top \mid \bot \mid \lnot C\mid C\sqcap D\mid C\sqcup D\mid \exists R.C\mid \forall R.C}$ 

CN es un nombre de concepto (conceptos atómicos) R es una expresión de rol.

El nombre de concepto ${\displaystyle \top }$  (top) representa el concepto más general. El nombre de concepto ${\displaystyle \bot }$  (bottom) representa el concepto menos general.

Semántica de ${\displaystyle {\mathcal {ALC}}}$ 

La Semántica busca explicar la relación que existe entre la sintaxis del lenguaje y los modelos previstos del dominio, dando significado a las expresiones, el cual es dado por el modelo teórico semántico. Este modelo teórico fue propuesto por Tarski, donde los conceptos y roles se refieren a conjuntos de objetos en el dominio de interés y las relaciones entre ellos.

Formalmente el modelo teórico se da por: ${\displaystyle {\mathcal {I}}=(\Delta ^{\mathcal {I}},\cdot ^{\mathcal {I}})}$  el cual consta de un conjunto no vacío ${\displaystyle \Delta ^{\mathcal {I}}}$  llamado el dominio de ${\displaystyle {\mathcal {I}}}$  y una función ${\displaystyle \cdot ^{\mathcal {I}}}$  (la función de interpretación de ${\displaystyle {\mathcal {I}}}$ ) que asigna a cada concepto un subconjunto de ${\displaystyle \Delta ^{\mathcal {I}}}$ , cada rol a un subconjunto de ${\displaystyle \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}}$  y a cada individuo un elemento de ${\displaystyle \Delta ^{\mathcal {I}}}$ , de tal manera que:

${\displaystyle \top ^{\mathcal {I}}=\Delta ^{\mathcal {I}}}$ 

${\displaystyle \bot ^{\mathcal {I}}=\emptyset }$ 

${\displaystyle (\lnot C)^{\mathcal {I}}=\Delta ^{\mathcal {I}}\backslash C^{\mathcal {I}}}$ 

${\displaystyle (C\sqcap D)^{\mathcal {I}}=C^{\mathcal {I}}\cap D^{\mathcal {I}}}$ 

${\displaystyle (C\sqcup D)^{\mathcal {I}}=C^{\mathcal {I}}\cup D^{\mathcal {I}}}$ 

${\displaystyle (\exists R.C)^{\mathcal {I}}=\{d\in \Delta ^{\mathcal {I}}\mid \exists e\in \Delta ^{\mathcal {I}}:(d,e)\in R^{\mathcal {I}}\land e\in C^{\mathcal {I}}\}}$ 

${\displaystyle (\forall R.C)^{\mathcal {I}}=\{d\in \Delta ^{\mathcal {I}}\mid \forall e\in \Delta ^{\mathcal {I}}:(d,e)\in R^{\mathcal {I}}\to e\in C^{\mathcal {I}}\}}$ 

Es decir:

• Un concepto es interpretado como un conjunto de individuos
• Los roles son interpretados como conjuntos de pares de individuos.
• Los conceptos atómicos se interpretan como subconjuntos del dominio de la interpretación.

Mientras que la Semántica de los constructores son entonces especificados por definiciones de conjunto de individuos denotados por cada constructor. Por ejemplo:

• ${\displaystyle C\sqcap D}$  es el conjunto de individuos obtenidos por la intersección de conjuntos de individuos denotados por C y D, respectivamente.
• ${\displaystyle \forall R.C}$  es el conjunto de individuos que están en la relación R con los individuos que pertenecen al conjunto denotado por el concepto C.

Extensiones de ${\displaystyle {\mathcal {ALC}}}$ 

El poder expresivo de una lógica de descripción es la capacidad para representar “conocimiento” acerca del dominio y depende de la riqueza de su lenguaje.

El lenguaje de la lógica ${\displaystyle {\mathcal {ALC}}}$  no es muy expresivo. Para comprobarlo basta ver estos ejemplos de “información” básica sobre un dominio sencillo no expresable en ${\displaystyle {\mathcal {ALC}}}$ :

• “Una mujer que tiene exactamente dos hijos” (no es posible expresar restricciones numéricas).
• “Todo hombre es hijo de una mujer” (no es posible expresar el inverso de un rol).
• “La madre del padre es la abuela” (no es posible expresar composición de roles).

Es necesario extender el lenguaje de ${\displaystyle {\mathcal {ALC}}}$ , pero añadiendo los elementos necesarios de forma que la complejidad computacional no sea intratable, ya que queremos poder razonar con esa lógica y, en particular, disponer de los algoritmos mínimos de satisfactibilidad, subsumición y consistencia. Veamos los constructores más importantes utilizados para extender el lenguaje ${\displaystyle {\mathcal {ALC}}}$  y también algunos de los sistemas obtenidos extendiéndola.

• Restricciones numéricas ${\displaystyle ({\mathcal {N}})}$  : ${\displaystyle \geq n\ R\mid \leq n\ R}$ 
• Restricciones numéricas cualificadas ${\displaystyle ({\mathcal {Q}})}$  : ${\displaystyle \geq n\ R.C\mid \leq n\ R.C}$ 
• Restricciones Funcionales ${\displaystyle ({\mathcal {F}})}$  : ${\displaystyle \leq 1\ R}$ 
• Nominales ${\displaystyle ({\mathcal {O}})}$  : ${\displaystyle a_{1},\ldots ,a_{n}}$ 
• Dominios concretos: Un dominio concreto D es un conjunto ${\displaystyle \Delta ^{(D)}}$  (el dominio) más un conjunto pred(D) de los nombres de predicado de D. Cada nombre de predicado P de D se asocia con una aridad n y un predicado n-ario de ${\displaystyle \Delta ^{(D)}}$ .

Ejemplo: el dominio concreto ${\displaystyle \mathbb {N} }$ , tiene como dominio el conjunto ${\displaystyle \mathbb {N} }$  de los números naturales y pred(${\displaystyle \mathbb {N} }$ ) el conjunto de los predicados binarios < ≤ > ≥ .

Las lógicas de descripción mucho más expresivas también emplean constructores de roles, dado que los roles se interpretan como relaciones binarias; esto implica definir constructores cuya Semántica es la de las operaciones sobre relaciones. Donde: si R y S son descripciones de rol (atómico) también lo son:

• Unión de roles: ${\displaystyle R\sqcup S}$ 
• Intersección de roles: ${\displaystyle R\sqcap S}$ 
• Complemento de rol: ${\displaystyle \lnot R}$ 
• Composición de roles: ${\displaystyle R\circ S}$ 
• Rol inverso ${\displaystyle ({\mathcal {I}})}$  : ${\displaystyle R^{-}}$ 
• Rol transitivo: ${\displaystyle R^{+}}$ 

La terminología también permite incluir jerarquía de roles ${\displaystyle ({\mathcal {H}})}$  donde los axiomas son de la forma:

${\displaystyle R\doteq S\mid R\sqsubseteq S}$ 

La semántica para las expresivas lógicas de descripción expuestas anteriormente se da; de la siguiente manera:

Axiomas	Semántica	Ejemplo
${\displaystyle \geq n\ R}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\}\geq n\}}$	${\displaystyle \geq 2\ tieneHijo}$
${\displaystyle \leq n\ R}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\}\leq n\}}$	${\displaystyle \leq 2\ tieneHijo}$
${\displaystyle \geq n\ R.C}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\land C^{\mathcal {I}}(y)\}\geq n\}}$	${\displaystyle \geq 3\ tieneHijo.Hombre}$
${\displaystyle \leq n\ R.C}$	${\displaystyle \{x\mid \#\{y\mid R^{\mathcal {I}}(x,y)\land C^{\mathcal {I}}(y)\}\leq n\}}$	${\displaystyle \leq 3\ tieneHijo.Mujer}$
${\displaystyle a_{1}\ldots a_{n}}$	${\displaystyle \{a_{1}^{\mathcal {I}},\ldots ,a_{n}^{\mathcal {I}}\}}$	${\displaystyle \{Maria,John\}}$
${\displaystyle R\sqcup S}$	${\displaystyle R^{\mathcal {I}}\cup S^{\mathcal {I}}}$	${\displaystyle tieneHijo\sqcup tieneHija}$
${\displaystyle R\sqcap S}$	${\displaystyle R^{\mathcal {I}}\cap S^{\mathcal {I}}}$	${\displaystyle tieneHijo\sqcap tieneHija}$
${\displaystyle \lnot R}$	${\displaystyle (\Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}})\mid R^{\mathcal {I}}}$	${\displaystyle \lnot tieneAmigo}$

Axiomas	Semántica	Ejemplo
${\displaystyle R\circ S}$	${\displaystyle \{(a,c)\in \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}\mid \exists b.(a,b)\in R^{\mathcal {I}}\land (b,c)\in S^{\mathcal {I}}\}}$	${\displaystyle tieneHijo\circ tieneAmigo}$
${\displaystyle R^{-}}$	${\displaystyle \{(b,a)\in \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}\mid (a,b)\in R^{\mathcal {I}}\}}$	${\displaystyle tienePadre^{-}}$
${\displaystyle R^{+}}$	${\displaystyle \bigcup _{i\geq 1}(R^{\mathcal {I}})^{i}}$	${\displaystyle ancestro^{+}}$
${\displaystyle R\doteq S}$	${\displaystyle R^{\mathcal {I}}=S^{\mathcal {I}}}$	${\displaystyle tieneHijo\doteq tienePadre^{-}}$
${\displaystyle R\sqsubseteq S}$	${\displaystyle R^{\mathcal {I}}\subseteq S^{\mathcal {I}}}$	${\displaystyle ancestro^{+}\sqsubseteq ancestro}$

Inferencias

Las lógicas de descripción son algo más que lenguajes para formalizar conceptos, deben representar la ontología de un dominio de aplicación y permitir razonar sobre él. Para ello se introducen nuevos elementos en el lenguaje y la semántica necesaria para formalizar las propiedades de los individuos del dominio y de las relaciones entre conceptos y roles, son las llamadas bases de conocimiento.

Base de conocimiento

La base de conocimiento está formada por dos componentes: el TBox y el ABox.

El TBox contempla toda la terminología, o sea, el vocabulario de un dominio de aplicación en función de:

• Conceptos: denotan clases o conjunto de individuos.
• Roles: denotan relaciones binarias entre los individuos.
• Un conjunto de descripciones complejas sobre este vocabulario (restringidos, por su puesto, por el lenguaje de descripción).

El ABox contiene aserciones acerca de individuos nombrados en términos de vocabulario.

Una base de conocimiento (TBox y ABox) es equivalente a un conjunto de axiomas de la LPO (Lógica de primer orden), y por tanto se puede definir un cálculo o sistema de inferencia que permite derivar “conocimiento” implícito a partir del “explícito” de la base de conocimiento.

Razonamiento con conceptos (TBox)

Supongamos que tenemos un lenguaje descriptivo para un dominio, por ejemplo ${\displaystyle {\mathcal {ALC}}}$ , y que se ha definido una TBox(axiomas terminológicos) para modelar un dominio. Si se define un nuevo concepto es importante saber si es consistente o contradictorio con el TBox. Esta propiedad se conoce como el concepto satisfacible (o respectivamente insatisfacible) con respecto al TBox. También puede ser necesario saber si un concepto es más general que otro, si son equivalentes o si son disjuntos. La formalización de estas propiedades es la siguiente:

Supongamos que ${\displaystyle {\mathcal {T}}}$  es un TBox, C y D conceptos:

• C es satisfactible con respecto a ${\displaystyle {\mathcal {T}}}$  si existe un modelo ${\displaystyle {\mathcal {I}}}$  tal que ${\displaystyle {\mathcal {T}}(C)^{\mathcal {I}}\neq \emptyset }$ .
• C es subsumido por D con respecto a ${\displaystyle {\mathcal {T}}}$  si para todo modelo ${\displaystyle {\mathcal {I}}}$  de ${\displaystyle {\mathcal {T}}}$ , tenemos que ${\displaystyle (C)^{\mathcal {I}}\subseteq (D)^{\mathcal {I}}}$ . Esto se escribe ${\displaystyle {\mathcal {T}}\models C\sqsubseteq D}$ .

Razonando con individuos (ABox)

Una vez definida una TBox, al definir el ABox, las propiedades más importantes que habrá que verificar son las de la consistencia del Abox y el TBox , y la derivación de una instanciación a partir del ABox. Veamos formalmente estos conceptos:

Supongamos que ${\displaystyle {\mathcal {T}}}$  es un TBox, A es un ABox, C un concepto y o un nombre de individuo:

• A es consistente con respecto a ${\displaystyle {\mathcal {T}}}$  si existe una interpretación que es modelo de ${\displaystyle {\mathcal {T}}}$  y de A.
• o:C se deriva de ${\displaystyle {\mathcal {T}}}$  y A si todo modelo ${\displaystyle {\mathcal {I}}}$  de ${\displaystyle {\mathcal {T}}}$  cumple ${\displaystyle (o)^{\mathcal {I}}\in (C)^{\mathcal {I}}}$ . esto es ${\displaystyle ({\mathcal {T}},A\models o:C)}$ .

Sistema ${\displaystyle {\mathcal {SH}}}$

Esta es otra notación muy utilizada por algunos sistemas de lógicas de descripción. La importancia de esta lógica, radica en que es la que actualmente se está implementando para las ontologías dependiendo de las necesidades del programador. El sistema ${\displaystyle {\mathcal {SH}}}$  se da de la siguiente manera:

${\displaystyle {\mathcal {SHIQ}}}$  es ${\displaystyle {\mathcal {ALCQI}}}$  + roles transitivos + inclusión roles. ${\displaystyle {\mathcal {SHOIQ}}}$  es ${\displaystyle {\mathcal {SHIQ}}}$  + nominales. Se demuestra también que ${\displaystyle {\mathcal {SHOIQ}}}$  es ${\displaystyle {\mathcal {SHOIN}}}$  extendida con restricciones cualificadas. ${\displaystyle {\mathcal {SHOIN(D)}}}$  es ${\displaystyle {\mathcal {ALCIN}}}$  + nominales + dominios concretos (${\displaystyle {\mathcal {D}}}$ ).

Aunque extender una lógica con dominios concretos la dota de una expresividad muy valorada para representar ontologías, fácilmente puede llevar a la indecidibilidad. Veremos, sin embargo, que ${\displaystyle {\mathcal {SHOIN(D)}}}$  es decidible y es base para el lenguaje de ontología actualmente más aceptado.

Complejidad computacional del sistema ${\displaystyle {\mathcal {SH}}}$ 

Las lógicas de descripción fueron pensadas como sistemas formales para representar conocimiento, y esto significa ir más allá de almacenar terminologías y descripciones. En particular, significa poder derivar hechos implícitos a partir de los dados. Por este motivo la implementación de procesos de inferencia debe tener en cuenta la posibilidad de usar algoritmos de inferencia óptimos. En el estudio de tales algoritmos el punto de partida es conocer su complejidad computacional (por ejemplo la complejidad EXPTIME y PSPACE).

Encontrar algoritmos de decisión para los problemas de inferencia como satisfactibilidad, subsumición y consistencia en ABoxes para lógicas de descripción expresivas y con la menor complejidad posible, de forma que la implementación computacional sea afrontable, la cual es todo un reto.

La búsqueda de estos procedimientos de decisión ha sido uno de los objetivos fundamentales en el desarrollo de las lógicas de descripción. Una de las maneras de obtenerlos es estudiando la conexión de las lógicas de descripción con otras lógicas conocidas. Es el caso de la decidibilidad en ${\displaystyle {\mathcal {ALC}}}$  y en todas sus extensiones que se obtienen añadiendo constructores que en la LPO se pueden expresar con dos variables. Sin embargo, la complejidad del procedimiento de decisión obtenido de esta manera es normalmente mayor del que realmente se necesita; por ejemplo el problema de satisfactibilidad para la LPO con dos variables es NEXPTIME (que es una complejidad muy grande, aunque todavía es decidible) mientras que en ${\displaystyle {\mathcal {ALC}}}$  es PSPACE-hard (es una complejidad menor). Otra manera de estudiar la complejidad es usando la conexión con las lógicas modales proposicionales.

En la siguiente tabla se presentara las principales extensiones de ${\displaystyle {\mathcal {ALC}}}$ , especificando las nuevas propiedades expresables en la extensión y los límites para la complejidad computacional.

DL	Propiedad expresable en la lógica	Complejidad
${\displaystyle {\mathcal {ALC}}}$	lógica de descripción básica	PSPACE
${\displaystyle {\mathcal {ALCN}}}$	+ restricciones numéricas no calificadas ${\displaystyle ({\mathcal {N}})}$	PSPACE
${\displaystyle {\mathcal {ALC}}}$ reg	+ expresiones regulares sobre roles (reg)	EXPTIME
${\displaystyle {\mathcal {ALCI}}}$ reg	+ inverso de roles ${\displaystyle ({\mathcal {I}})}$	EXPTIME
${\displaystyle {\mathcal {ALCFI}}}$ reg	+ restricciones funcionales sobre roles atómicos ${\displaystyle ({\mathcal {F}})}$	EXPTIME
${\displaystyle {\mathcal {ALCQI}}}$ reg	+ restricciones numéricas calificadas ${\displaystyle ({\mathcal {Q}})}$	EXPTIME
${\displaystyle {\mathcal {ALCQO}}}$ reg	+ un alfabeto para los objetos del dominio ${\displaystyle ({\mathcal {O}})}$	EXPTIME
${\displaystyle {\mathcal {SHIQ}}}$	${\displaystyle {\mathcal {ALCQI}}}$  + roles transitivos + inclusión roles	EXPTIME
${\displaystyle {\mathcal {SHOIN}}}$	+ restricciones numéricas no calificadas ${\displaystyle ({\mathcal {N}})}$	EXPTIME
${\displaystyle {\mathcal {SHOIQ}}}$	${\displaystyle {\mathcal {SHIQ}}}$  + nominales	NEXPTIME
${\displaystyle {\mathcal {SHOIN(D)}}}$	${\displaystyle {\mathcal {SHOIN}}}$  + dominios concretos	EXPTIME

Este un libro relaciona 16 clases de complejidad algorítmica respecto a espacio y tiempo. Y resuelve algunas igualdades.

Véase también

• Web semántica
• Ontología (Informática)
• DAML+OIL
• OWL
• RACER system
• KAON

Bibliografía

• F. Baader, D. Calvanese, D. L. McGuiness, D. Nardi, P. F. Patel-Schneider: The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press, Cambridge, UK, 2003. ISBN 0-521-78176-0

Enlaces externos

• http://dl.kr.org/
• Curso Introduction to Description Logics
• Navigator on Description Logic Complexity

•   Datos: Q387196