miércoles, julio 20, 2005

Tema de tesis

Creo que nunca he puesto nada técnico en este blog, pero después del difícil proceso de decisión para escoger un tema de tesis, me parece una buena idea intentar describir de qué va a tratar ésta. Espero que esto no resulte muy tedioso para el respetable :P.
Hace 10 meses, antes de llegar a Alemania, yo no sabía absolutamente nada de autómatas, y mis conocimientos de teoría de la complejidad eran absolutamente básicos. Ahora, he decidido hacer mi tesis sobre las condiciones que debe cumplir un autómata sobre árboles para que el problema de decidir si el lenguaje del autómata es vacío se pueda resolver utilizando espacio logarítmico.
Sé que la frase anterior resulta difícil de entender, por lo que quiero explicar un poco de qué se trata, y la motivación del mismo.
Es una práctica común actualmente utilizar autómatas para demostrar algunos resultados, sobre todo de decidibilidad (dificil palabra) en lógica. Por ejemplo, en lógica temporal lineal, se puede ver el estado con el paso del tiempo como una palabra infinita; así, si se quiere saber si alguna fórmula se satisface en esta lógica, se puede ver si cierto autómata (construído apropiadamente a partir de la fórmula) acepta alguna palabra. De igual forma, si se tiene lógica temporal que tiene ramificaciones al futuro, se utilizan autómatas que leen árboles.
El problema con este punto de vista es que la construcción del autómata es comúnmente exponencial, y muchas veces el problema de satisfacción no requiere tanta complejidad. Por ejemplo, en lógica temporal lineal, el problema de satisfacción es bien sabido que es PSpace-completo (o sea, requiere un espacio polinomial para ser resuelto). Entonces, cómo usar autómatas para obtener resultados similares?
Lo que se hace es que no se construye realmente el autómata completo, sino que se demuestra que se puede ir construyendo "según se necesite", y que la información necesaria en todo momento para hacer esta construcción, y mantener el estado adecuadamente, es polinomial. Además, debe existir una cota en la profundidad del árbol (un resultado intermedio que requiera que, si el autómata acepta un árbol, entonces debe aceptar un árbol de a lo más cierta profundidad) que se requiere también sea polinomial.
Lo que se logra con esto es probar que se puede utilizar espacio logarítmico en el tamaño del autómata (que viene a ser polinomial en el tamaño del problema original) para resolver el problema.
Estas demostraciones son comúnes, pero cada vez que se requiere, se hace una nueva "a la medida" para la lógica y el autómata en cuestión.
La idea para mi tesis es encontrar condiciones suficientes para que un autómata acepte una solución en espacio logarítmico del problema. De esta forma, cada vez que se quiera demostrar que el problema de satisfacción de cierta lógica está en PSpace utilizando técnicas de autómatas, simplemente se tiene que demostrar que el autómata en cuestión cumple estas condiciones.
Si da tiempo, y todavía tenemos ganas de seguir en esto, vamos a hacer lo mismo para otras clases de complejidad, como ExpTime. Ahí uno se topa con más problemas porque, mientras PSpace = NPSpace, ExpTime =/= NExpTime, y algunas de las técnicas (en particular, el clásico "adivino los estados que toma el autómata para aceptar este árbol" ya no son válidos, pues mandan directamente a la clase no-determinista.

Espero haber sido claro en mi explicación, si cualquiera está interesado, o tiene dudas, por favor no duden en contactarme.
Si no los aburrí demasiado, estoy pensando en tal vez poner una serie de posts explicando las bases de la teoría de autómatas, que es bastante básica.

5 comentarios:

Anónimo dijo...

Está interesante, aunque en realidad no le entendí completamente (bueno, luego lo leo con mayor atención) y eso que en mi tesis la estructura de datos que resuelve todo el problema es un autómata, je, je. Bueno, es que no hizo falta meterme con la teoría, pero me gustan esos temas.

Anónimo dijo...

Olvidé poner mi nombre en el comentario anterior.
Yixus

El hombre sonriente dijo...

En realidad solo entendí que deseas usar un autómata para probar "algo". Me interesaría saber más, pero por el amor del cielo apiadate de los ignorantes... No entendí el concepto de tiempo exp y otros tiempos que manejas. Tiene que ver con el tiempo de satisfacer una solución o encontrarla. Tampoco entendí que es la logica lineal... hay otras lógicas... Si vas a publicar más posts haste la idea de hacerlos entendibles, pues así tu mismo entenderás de que trata tu tesis. Por cierto te recomiendo los libros de Neal "Stephenson"... Son muy buenos... Hablan mucho en un sentido "obvio" de nanotecnología, autómatas y criptografía.

""-- aproximación fonética

sakuragi dijo...

hola que tal.

Tienes algo de PSpace completo o no?

sabes unos problemas interesante que sean PSPACE?

saludos

gracias.

sakuragi
ssakuragi2@hotmail.com

Rafael Peñaloza dijo...

Hola Sakuragi... pues yo estoy muy metido en logica descriptiva, asi que los problemas PSpace completos que conozco son sobre eso. Satisficibilidad de conceptos de la logica ALC con respecto a cajas terminologicas (TBoxes) que sean aciclicas (o vacias) es PSpace-completo.
Por supuesto hay muchos otros problemas, por ejemplo QBF.
Espero te ayude.