Thème de la théorie des automates / du langage formel

10

Salut à tous, j'essaie actuellement de trouver un sujet de thèse de master solide se rapportant à une branche de la théorie des automates ou lié aux langages formels. J'essaie de générer de bonnes idées sur ce qu'est un sujet acceptable, quelque chose d'ambitieux mais quelque chose de faisable en même temps.

Toutes les suggestions seraient très appréciés!

ds.algorithms automata-theory fl.formal-languages soft-question Vincent Russo
la source
3
En général, dans des questions comme celle-ci, il serait très utile de spécifier quel type de thèse vous êtes censé rédiger: par exemple, BSc, MSc, PhD, autre chose? En particulier, es-tu censé faire de nouvelles recherches ou "simplement" organiser les connaissances existantes?
Jukka Suomela
1
Je m'excuse de ne pas l'avoir précisé, je l'ai modifié ci-dessus pour montrer que c'est pour mon MSc. Autant que je sache, toutes les thèses doivent apporter de nouveaux résultats / recherches et ne sont pas seulement une organisation des connaissances existantes. Donc quelque chose dans cette ruelle si vous avez des suggestions.
Vincent Russo

Réponses:

9

Bien que je sois d'accord avec la réponse de David Eppstein en général (et j'ai voté en faveur), le domaine émergent des automates qui définissent les processus biologiques et d'autres «choses» informatiques naturelles est un domaine dynamique. Je ne peux pas m'engager plus tard, mais vous pourriez être intéressé par la biochimie artificielle de Luca Cardelli ou le calcul universel efficace de Turing avec des polymères d'ADN de Qian et al. Le premier article est la dernière tentative de Cardelli pour fournir des méthodes formelles aux processus biochimiques; le second, une implémentation théorique d'ADN d'une machine à empiler.

Aaron Sterling
la source
1
En ce qui concerne l'aspect pratique de l'embauche du mérite de mon sujet de thèse, je ne suis pas trop préoccupé. Je trouve ces sujets très intéressants et je préfère consacrer mon temps à quelque chose qui me passionne plutôt qu'à quelque chose qui me procurera un chèque de paie plus gros. Cela dit, j'aime l'idée sur le thème biologique. Je suis également un grand fan de l'informatique quantique, mais je ne suis pas sûr de ce qu'une thèse de maîtrise pourrait vraiment impliquer sur la complexité quantique.
Vincent Russo
Les problèmes sont également différents et plus difficiles à résoudre que le travail classique des années 70: les problèmes informatiques naturels ont tendance à ne pas être des problèmes classiques d'analyse de chaîne, mais généralement sur des graphiques acycliques. Recherchez "graph grammars natural computing".
Charles Stewart
1
En effet un sujet intéressant. Une autre branche du biocomputing (avec laquelle j'ai été impliqué) en dehors du déplacement de brins d'ADN du projet moléculaire- programming.org a étudié l' aspect "programmation" du domaine du biocomputing: diku.dk/~neil/blobentcs.pdf . À mon avis, cela vaut la peine d'être examiné :)
svrist
1
@svrist, Merci beaucoup d'avoir publié le lien vers Hartmann et al. papier. Je vais le lire aujourd'hui. Cela ressemble à la réponse à la question que j'ai posée ici: cstheory.stackexchange.com/questions/114/… donc vous venez de faire ma journée. :-)
Aaron Sterling
18

Je pense que David Eppstein est trop dédaigneux du domaine de la théorie des automates et des langages formels. L'affirmation selon laquelle "le faire publier dans des conférences de haut niveau et convaincre quelqu'un de vous embaucher une fois que vous aurez obtenu votre diplôme peut être problématique" semble être ce que Haldane a appelé le théorème de tante Jobiska: "C'est un fait que le monde entier sait."

En fait, il existe de bonnes conférences (telles que STACS et ICALP) qui publient régulièrement des résultats dans la théorie des automates et les langages formels; il existe des conférences très fréquentées (comme le DLT) qui se concentrent sur le domaine; c'est une zone très active en Allemagne, en France et en Italie; il y a de grands problèmes ouverts dans la région; et je connais beaucoup d'étudiants qui n'ont eu aucun problème à trouver un emploi.

Jeffrey Shallit
la source
1
C'est rassurant, vu que la théorie des automates et les langages formels sous-tendent tout ce qui est concevable dans le domaine de l'informatique, ce n'est pas trop surprenant non plus. En ce qui concerne le marché du travail, je n'y investis pas mon temps parce que je me soucie de gagner de l'argent, je le fais parce que je suis passionné par le sujet. Merci pour les suggestions.
Vincent Russo
1
D'ailleurs, existe-t-il de bons référentiels en ligne pour ces problèmes ouverts dont vous parlez? J'en ai trouvé quelques-uns ici et là, mais la plupart d'entre eux mentionnent les sujets théoriques les plus "commerciaux" de l'informatique. ie NP? = P etc. Merci encore pour l'aide.
Vincent Russo
3
@Captainhampton: Vous voudrez peut-être essayer de parcourir les actes de conférences comme STACS et ICALP (comme mentionné dans la réponse de Jeffrey) pour rechercher les derniers travaux et résoudre les problèmes qui en découlent. De bons sujets de thèse peuvent souvent être trouvés en utilisant cette méthode.
Ryan Williams
10

Aider avec le sujet de thèse est l'une des raisons pour lesquelles nous avons des superviseurs pour les étudiants diplômés, vous devriez donc consulter votre superviseur à ce sujet.

Le conseil général que j'ai entendu est que vous devriez choisir les actes d'un certain nombre de conférences récentes de bonne réputation dans le domaine dans lequel vous voulez travailler et jeter un coup d'œil aux documents qu'ils contiennent jusqu'à ce que vous trouviez quelque chose d'intéressant et en discutez avec votre superviseur pour voir si c'est un sujet de thèse raisonnable.

Kaveh
la source
1
Merci pour les commentaires Kaveh. Je me suis entretenu d'avant en arrière avec mon conseiller, mais en fin de compte, c'est à moi de décider, car ce sera moi qui consacrerai l'essentiel de son temps à la matière. Donc, juste curieux de savoir si quelqu'un ici a eu de bonnes expériences de thèse avec le sujet. Peut-être quelque chose se rapportant à la complexité quantique, mais une «taille de morsure» suffisante pour un niveau de mémoire de maîtrise.
Vincent Russo
7

Un autre domaine fructueux non mentionné ici est le lien entre la théorie des automates et la logique. Je suppose que cette direction de recherche est plus populaire en Europe qu'en Amérique du Nord. Comme je ne travaille pas dans ce domaine, je ne peux pas vous suggérer de problème spécifique. Mais vous pouvez consulter les récents LICS 2010 ainsi que les précédents pour les travaux récents. Les notes de cours d'un cours de Leonid Libkin sont un bon point de départ.

Dai Le
la source
4
À titre d'exemple, l'étude des langages de mots imbriqués qui sont reconnus par les automates visuellement déroulants a attiré beaucoup d'attention au cours de la dernière décennie. L'une des raisons est qu'il s'agit d'un bon modèle de nombreux problèmes liés à XML, une autre est que le modèle sert à relier les travaux dans plusieurs domaines différents (théorie du langage de programmation, vérification logicielle, concurrence, logique). Il semble que ce soit l'un de ces sujets qui franchissent véritablement le fossé A / B. cis.upenn.edu/~alur/nw.html
András Salamon
6

L'étude théorique de la théorie des automates et des langages formels est un peu moribonde (ce qui signifie que vous pouvez probablement encore trouver des problèmes de recherche intéressants sur lesquels travailler, mais le faire publier dans des conférences de haut niveau et convaincre quelqu'un de vous embaucher une fois votre diplôme peut être problématique) . Cependant, je pense qu'il y a également un travail intéressant en cours sur l'application de la théorie formelle du langage à la détection des menaces / intrusions sur Internet, etc., et ce domaine semble beaucoup plus brûlant en ce moment.

Voir par exemple

Wagner et Dean, Détection d'intrusions via l'analyse statique, IEEE Symp. Sécurité et confidentialité 2001

Wagner et Soto, Mimicry attack on host-based intrusion detection systems, ACM Conf. Sécurité informatique et des communications 2002

Giffin, Jha et Miller, Détection efficace des intrusions contextuelles, NDSS 2004

Feng et al, Formaliser la sensibilité dans l'analyse statique pour la détection des intrusions, Symposium IEEE sur la sécurité et la confidentialité 2004

David Eppstein
la source
1
Je suis d'accord pour dire que l'aspect pratique du marché du travail de la théorie des automates fait défaut, mais les applications de la théorie sont assez nombreuses comme vous l'avez montré. Merci pour les recommandations. Y a-t-il d'autres sujets applicables aux automates, sans inclure la sécurité, que vous pourriez recommander? J'aimerais vraiment faire quelque chose avec la théorie de la complexité quantique, mais je pense que cela peut être un peu ambitieux pour un projet de maîtrise (peut-être un doctorat).
Vincent Russo
3
David aussi, je pense que vous donnez un bref aperçu des méthodes formelles utilisées dans la vérification. Surtout quand il s'agit de choses comme les automates Buchi, il y a toutes sortes de questions intéressantes. Ils viennent de s'éloigner de la terre STOC / FOCS / SODA.
Suresh Venkat