Teoría de Autómatas / Tema de Tesis de Lenguaje Formal

10

Hola a todos, actualmente estoy tratando de encontrar un tema de tesis de maestría sólido relacionado con alguna rama de la teoría de autómatas o relacionada con lenguajes formales. Estoy tratando de generar algunas buenas ideas sobre lo que sería un tema aceptable, algo ambicioso pero algo factible al mismo tiempo.

Cualquier sugerencia sería muy apreciada!

ds.algorithms automata-theory fl.formal-languages soft-question Vincent Russo
fuente
3
En general, en preguntas como esta, sería muy útil especificar qué tipo de tesis se supone que debes escribir: por ejemplo, BSc, MSc, PhD, ¿algo más? En particular, ¿se espera que realice una nueva investigación o "simplemente" organice el conocimiento existente?
Jukka Suomela
1
Pido disculpas por no especificar, lo he editado arriba para mostrar que es para mi maestría. Por lo que puedo decir, todas las tesis deben contribuir con nuevos resultados / investigación y no son solo una organización de conocimiento existente. Así que algo en ese callejón si tienes alguna sugerencia.
Vincent Russo

Respuestas:

9

Si bien estoy de acuerdo con la respuesta de David Eppstein en general (y lo voté), el campo emergente de autómatas que define procesos biológicos y otras "cosas" de computación natural es un área vibrante. Ser contratado más tarde no es algo con lo que pueda hablar, pero es posible que le interese echar un vistazo a la Bioquímica Artificial de Luca Cardelli, o el cálculo universal eficiente de Turing con polímeros de ADN de Qian et al. El primer artículo es el último intento de Cardelli de proporcionar métodos formales para los procesos bioquímicos; el segundo, una implementación teórica de ADN de una máquina apiladora.

Aaron Sterling
fuente
1
En cuanto a la practicidad de contratar el mérito de mi tema de tesis, no estoy demasiado preocupado. Considero que estos temas son muy interesantes y preferiría dedicar mi tiempo a algo que me apasione en lugar de algo que me dé un cheque de pago más gordo. Dicho esto, me gusta la idea de temática biológica. También soy un gran admirador de la computación cuántica, pero no estoy seguro de lo que realmente podría implicar una tesis de nivel de maestría en la complejidad cuántica.
Vincent Russo el
Los problemas también son diferentes y más difíciles para el trabajo clásico de los 70: los problemas informáticos naturales tienden a no ser problemas clásicos de análisis de cadenas, sino que generalmente son gráficos acíclicos. Busque "gramáticas gráficas computación natural".
Charles Stewart
1
De hecho, un tema interesante. Otra rama de la biocomputación (en la que he estado involucrado) fuera del desplazamiento de la cadena de ADN del proyecto molecular-programming.org ha estado investigando el aspecto de "programación" del dominio de la biocomputación: diku.dk/~neil/blobentcs.pdf . En mi opinión sesgada vale la pena mirar :)
svrist
1
@svrist, Muchas gracias por publicar el enlace a Hartmann et al. papel. Lo leeré hoy. Parece la respuesta a la pregunta que hice aquí: cstheory.stackexchange.com/questions/114/… así que me alegraron el día. :-)
Aaron Sterling
18

Creo que David Eppstein es demasiado desdeñoso en el área de la teoría de autómatas y los lenguajes formales. La afirmación de que "publicarlo en conferencias de alto nivel y convencer a alguien para que lo contrate una vez que se gradúe puede ser problemático" parece ser lo que Haldane llamó el teorema de tía Jobiska: "Es un hecho que todo el mundo sabe".

De hecho, hay buenas conferencias (como STACS e ICALP) que publican habitualmente resultados en teoría de autómatas y lenguajes formales; hay conferencias muy concurridas (como DLT) que se centran en el área; Es un área muy activa en Alemania, Francia e Italia; hay grandes problemas abiertos en el área; y conozco a muchos estudiantes que no han tenido problemas para conseguir trabajo.

Jeffrey Shallit
fuente
1
Eso es tranquilizador, ya que la teoría de los autómatas y los lenguajes formales subyacen a todo lo concebiblemente hecho en el campo de la informática tampoco es demasiado sorprendente. En lo que respecta al mercado laboral, no estoy invirtiendo mi tiempo en esto porque me importa ganar dinero, lo hago porque me apasiona el tema. Gracias por las sugerencias
Vincent Russo
1
Por cierto, ¿hay algún buen repositorio en línea para estos problemas abiertos que mencionas? He encontrado algunos aquí y allá, pero la mayoría de ellos indican los temas teóricos más "comerciales" de informática. es decir, NP? = P, etc. Gracias de nuevo por la ayuda.
Vincent Russo el
3
@Captainhampton: es posible que desee examinar las actas de conferencias como STACS e ICALP (como se menciona en la respuesta de Jeffrey) para buscar el último trabajo y resolver los problemas derivados de ellas. Los buenos temas de tesis a menudo se pueden encontrar utilizando este método.
Ryan Williams
10

Ayudar con el tema de tesis es una de las razones por las que tenemos supervisores para estudiantes graduados, por lo que debe consultar a su supervisor al respecto.

El consejo general que he escuchado es que debe elegir las actas de varias conferencias recientes de buena reputación en el área en la que desea trabajar y echar un vistazo a los documentos en ellas hasta encontrar algo interesante y discutirlo con su supervisor para ver si Es un tema de tesis razonable.

Kaveh
fuente
1
Gracias por los comentarios Kaveh. He estado hablando de un lado a otro con mi asesor, pero en última instancia la decisión depende de mí, ya que seré yo quien dedique la mayor parte de su tiempo al tema. Tan curioso si alguien aquí tuvo alguna buena experiencia de tesis con el tema. Posiblemente algo relacionado con la complejidad cuántica pero "tamaño de mordida" suficiente para un nivel de tesis de maestría.
Vincent Russo el
7

Otra área fructífera que ya no se menciona aquí es la conexión entre la teoría de autómatas y la lógica. Supongo que esta dirección de investigación es más popular en Europa que en Norteamérica. Como no trabajo en ese campo, no puedo sugerirle un problema específico. Pero puede consultar los recientes LICS 2010 y los anteriores para trabajos recientes. Las notas de clase de un curso de Leonid Libkin es un buen lugar para comenzar.

Dai Le
fuente
44
Como ejemplo, el estudio de lenguajes de palabras anidadas que son reconocidos por autómatas visiblemente pushdown ha atraído mucha atención en la última década. Una razón es que este es un buen modelo de muchos problemas relacionados con XML, otra es que el modelo sirve para unir el trabajo en varias áreas diferentes (teoría del lenguaje de programación, verificación de software, concurrencia, lógica). Parece ser uno de esos temas que realmente cruzan la división A / B. cis.upenn.edu/~alur/nw.html
András Salamon
6

El estudio teórico de la teoría de autómatas y los lenguajes formales es algo moribundo (lo que significa que probablemente todavía pueda encontrar problemas de investigación interesantes para trabajar, pero publicarlo en conferencias de alto nivel y convencer a alguien para que lo contrate una vez que se gradúe puede ser problemático) . Sin embargo, creo que también se está haciendo un trabajo interesante sobre la aplicación de la teoría del lenguaje formal para la detección de intrusos / amenazas de Internet, etc., y esta área parece mucho más actual en este momento.

Ver por ej.

Wagner y Dean, Detección de intrusos mediante análisis estático, IEEE Symp. Seguridad y privacidad 2001

Wagner y Soto, Mimicry ataca sistemas de detección de intrusos basados ​​en host, ACM Conf. Seguridad informática y de comunicaciones 2002

Giffin, Jha y Miller, Detección de intrusión eficiente sensible al contexto, NDSS 2004

Feng et al, Formalizing Sensitivity in Static Analysis for Intrusion Detection, IEEE Symposium on Security and Privacy 2004

David Eppstein
fuente
1
Estoy de acuerdo en que falta la practicidad en el mercado laboral de la teoría de autómatas, sin embargo, las aplicaciones de la teoría son bastante numerosas, como ha demostrado. Gracias por las recomendaciones. ¿Existen otros temas de autómatas aplicables que no incluyan la seguridad que pueda recomendar? Realmente me gustaría hacer algo con la teoría de la complejidad cuántica, pero creo que puede ser un poco ambicioso para un proyecto de maestría (quizás un doctorado).
Vincent Russo
3
También David, creo que le das poca importancia a los métodos formales que se usan en la verificación. Especialmente cuando se trata de cosas como los autómatas de Buchi, hay todo tipo de preguntas interesantes. Se acaban de mudar de la tierra STOC / FOCS / SODA.
Suresh Venkat