Teoria de Autômatos / Tese de Linguagem Formal

10

Olá pessoal, Atualmente, estou tentando encontrar um tópico sólido de tese de mestrado referente a algum ramo da teoria dos autômatos ou relacionado a linguagens formais. Estou tentando gerar boas idéias para o que seria um tópico aceitável, algo ambicioso, mas algo factível ao mesmo tempo.

Quaisquer sugestões seriam muito apreciadas!

ds.algorithms automata-theory fl.formal-languages soft-question Vincent Russo
fonte
3
Em geral, em questões como essa, seria muito útil especificar que tipo de tese você deveria escrever: Por exemplo, bacharelado, mestrado, doutorado, alguma outra coisa? Em particular, você espera fazer novas pesquisas ou "apenas" organizar o conhecimento existente?
Jukka Suomela
11
Peço desculpas por não especificar, editei-o acima para mostrar que é para o meu mestrado. Até onde sei, todas as teses devem contribuir com novos resultados / pesquisa e não são apenas uma organização do conhecimento existente. Então, algo nesse beco, se você tiver alguma sugestão.
Vincent Russo

Respostas:

9

Embora eu concorde com a resposta de David Eppstein em geral (e eu a votei), o emergente campo de autômatos que define processos biológicos e outras "coisas" naturais da computação é uma área vibrante. Ser contratado mais tarde não é algo com o qual eu possa falar, mas você pode estar interessado em dar uma olhada na Bioquímica Artificial de Luca Cardelli ou no cálculo universal eficiente de Turing com polímeros de DNA de Qian et al. O primeiro artigo é a mais recente tentativa de Cardelli de fornecer métodos formais para processos bioquímicos; o segundo, uma implementação teórica de DNA de uma máquina de empilhar.

Aaron Sterling
fonte
11
Quanto à praticidade de contratar mérito no meu tópico de tese, não estou muito preocupado. Acho esses tópicos muito interessantes e preferiria dedicar meu tempo a algo pelo qual sou apaixonada, em vez de algo que me traga um cheque mais salgado. Com isso dito, eu gosto da idéia temática biológica. Eu também sou um grande fã da computação quântica, mas não tenho certeza do que uma tese de nível de mestrado poderia realmente implicar na complexidade quântica.
Vincent Russo
Os problemas também são diferentes e mais difíceis para o trabalho clássico dos anos 70: problemas de computação natural tendem a não ser problemas clássicos de análise de cordas, mas geralmente em gráficos acíclicos. Procure "gramáticas gráficas computação natural".
Charles Stewart
11
De fato, um tópico interessante. Outro ramo da biocomputação (com o qual estive envolvido) fora do deslocamento da fita de DNA do projeto molecular-programming.org está analisando o aspecto "programação" do domínio da biocomputação: diku.dk/~neil/blobentcs.pdf . Na minha opinião vale a pena tendenciosa olhando para :)
svrist
11
@ Chris, Muito obrigado por postar o link para o Hartmann et al. papel. Vou ler hoje. Parece a resposta para a pergunta que fiz aqui: cstheory.stackexchange.com/questions/114/… então você acabou de fazer o meu dia. :-)
Aaron Sterling
18

Penso que David Eppstein é muito desprezador da área da teoria dos autômatos e das linguagens formais. A afirmação de que "publicá-lo em conferências de alto nível e convencer alguém a contratá-lo depois que você se formar pode ser problemática" parece ser o que Haldane chamou de Teorema da tia Jobiska: "É um fato que o mundo inteiro sabe".

De fato, existem boas conferências (como STACS e ICALP) que publicam rotineiramente resultados na teoria dos autômatos e linguagens formais; há conferências bem assistidas (como DLT) que se concentram na área; é uma área muito ativa na Alemanha, França e Itália; existem grandes problemas em aberto na área; e conheço muitos estudantes que não tiveram problemas para conseguir emprego.

Jeffrey Shallit
fonte
11
Isso é reconfortante, visto que a teoria dos autômatos e as linguagens formais subjacentes a tudo o que é concebível feito no campo da ciência da computação também não é tão surpreendente. No que diz respeito ao mercado de trabalho, não estou investindo meu tempo nisso porque me preocupo com ganhar dinheiro, estou fazendo isso porque sou apaixonada pelo assunto. Obrigado pelas sugestões.
Vincent Russo
11
A propósito, existem bons repositórios online para esses problemas em aberto mencionados? Encontrei alguns aqui e ali, mas a maioria deles declara os tópicos teóricos mais "comerciais" da ciência da computação. NP? = P etc. Obrigado novamente pela ajuda.
Vincent Russo
3
@ Captainhampton: Você pode tentar navegar nos procedimentos de conferências como STACS e ICALP (como mencionado na resposta de Jeffrey) para procurar os trabalhos mais recentes e os problemas em aberto que surjam deles. Os tópicos de boa tese geralmente podem ser encontrados usando esse método.
Ryan Williams
10

Ajudar com o tópico da tese é um dos motivos pelos quais temos supervisores para estudantes de pós-graduação, portanto, consulte seu supervisor.

O conselho geral que ouvi é que você deve escolher uma série de conferências respeitáveis ​​recentes na área em que deseja trabalhar e dar uma olhada nos documentos nelas até encontrar algo interessante e discuti-lo com seu supervisor para verificar se é um tópico de tese razoável.

Kaveh
fonte
11
Obrigado pelo feedback Kaveh. Eu tenho conversado repetidamente com meu orientador, mas, no final das contas, a decisão é minha, pois eu dedico a maior parte de seu tempo no assunto. Então, só estou curioso para saber se alguém aqui teve alguma boa tese de experiência com o assunto. Possivelmente algo relacionado à complexidade quântica, mas "tamanho da mordida" suficiente para um nível de tese de mestrado.
Vincent Russo
7

Outra área frutífera ainda não mencionada aqui é a conexão entre a teoria dos autômatos e a lógica. Eu acho que essa direção de pesquisa é mais popular na Europa do que na América do Norte. Como não trabalho nesse campo, não posso sugerir um problema específico. Mas você pode conferir o LICS 2010 recente e os anteriores para trabalhos recentes. As notas de aula de um curso de Leonid Libkin são um bom lugar para começar.

Dai Le
fonte
4
Como exemplo, o estudo de linguagens de palavras aninhadas que são reconhecidas por autômatos visíveis de empilhamento atraiu muita atenção na última década. Uma razão é que este é um bom modelo de muitos problemas relacionados ao XML, outra é que o modelo serve para unir o trabalho em várias áreas diferentes (teoria da linguagem de programação, verificação de software, concorrência, lógica). Parece ser um daqueles tópicos que realmente cruzam a divisão A / B. cis.upenn.edu/~alur/nw.html
András Salamon
6

O estudo teórico da teoria dos autômatos e das linguagens formais é meio moribundo (o que significa que você provavelmente ainda pode encontrar problemas interessantes de pesquisa para trabalhar, mas publicá-lo em conferências de alto nível e convencer alguém a contratá-lo depois que você se formar pode ser problemático) . No entanto, acredito que também esteja sendo feito um trabalho interessante sobre a aplicação da teoria formal da linguagem à detecção de ameaças / intrusões na Internet etc., e essa área parece muito mais quente no momento.

Veja por exemplo

Wagner e Dean, detecção de intrusão por análise estática, IEEE Symp. Segurança e Privacidade 2001

Wagner e Soto, ataques de imitação em sistemas de detecção de intrusão baseados em host, ACM Conf. Segurança de computadores e comunicações 2002

Giffin, Jha e Miller, detecção eficiente de intrusões sensíveis ao contexto, NDSS 2004

Feng et al, Formalizando a sensibilidade na análise estática para detecção de intrusões, Simpósio IEEE sobre segurança e privacidade 2004

David Eppstein
fonte
11
Concordo que falta praticidade no mercado de trabalho da teoria dos autômatos, mas as aplicações da teoria são bastante numerosas, como você demonstrou. Obrigado pelas recomendações. Existem outros tópicos de autômatos aplicáveis ​​que não incluem a segurança que você pode recomendar? Eu realmente gostaria de fazer algo com a teoria da complexidade quântica, mas acredito que pode ser um pouco ambicioso para um projeto de mestrado (talvez um doutorado).
Vincent Russo
3
Também David, acho que você dá pouca atenção aos métodos formais usados ​​na verificação. Especialmente ao envolver coisas como o autômato Buchi, existem todos os tipos de perguntas interessantes. Eles acabaram de se mudar da terra STOC / FOCS / SODA.
Suresh Venkat