Resumen:
Las lógicas híbridas son una familia de lógicas modales que incorporan algunas nociones de identidad. Se caracterizan por incluir constantes (nominales) y, generalmente, algunos operadores híbridos, como @ σ ↓ . El primero, llamado operador de satisfacción, permite indicar explícitamente el individuo sobre el cual se predica. El segundo se puede ver como un mecanismo de asignar nombres a individuos de manera dinámica. En esta tesis investigamos el efecto que tiene, en términos de complejidad computacional, el agregado de nominales y operadores híbridos a una lógica modal (proceso conocido como hibridizacion), con el foco puesto en el operador ↓. Es sabido que este es un operador sumamente expresivo: mientras la lógica modal básica es PSPACE-completa, al hibridizarla únicamente con este operador obtenemos una lógica indecidible. Nuestro objetivo es estudiar hibridizaciones de lógicas modales sub-booleanas (i.e. que no incluyan un conjunto adecuado de operadores booleanos) para así delinear de manera más precisa la expresividad de este operador. Para ello extendemos con operadores híbridos a NL, un cálculo presentado por Lambek en la década del 60, similar a un sistema de tipos simple para el cálculo-lambda, utilizado en lingüística computacional. Este cálculo puede ser visto alternativamente como una lógica modal sin estructura booleana. El problema de derivabilidad (o, alternativamente, entailment lógico) en este cálculo puede ser resuelto en tiempo polinomial. NL es parte de una familia de lógicas llamadas CategorialType Logics (CTL). Utilizando un sistema de inferencia basado en tableaux, y traducciones de lógicas conocidas, damos resultados de complejidad para las hibridizaciones de NL que llamamos hCTL(@), hCTL(@; ↓) y hCTL( ↓). En particular, podemos ver que esta última también es indecidible. Este es un resultado sorprendente, teniendo en cuenta la bajísima expresividad de la lógica hibridizada.
Citación:
---------- APA ----------
Koile, Daniel. (2008). Complejidad computacional de lógicas híbridas sub-booleanas. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000420_Koile
---------- CHICAGO ----------
Koile, Daniel. "Complejidad computacional de lógicas híbridas sub-booleanas". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2008.https://hdl.handle.net/20.500.12110/seminario_nCOM000420_Koile
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000420_Koile.pdf
Distrubución geográfica
