Teoria automatów / Formalna teza językowa Temat

10

Cześć wszystkim, obecnie staram się znaleźć solidny temat pracy magisterskiej dotyczący jakiejś gałęzi teorii automatów lub związany z językami formalnymi. Próbuję wygenerować kilka dobrych pomysłów na temat akceptowalnego tematu, czegoś ambitnego, ale jednocześnie wykonalnego.

Wszelkie sugestie będą mile widziane!

ds.algorithms automata-theory fl.formal-languages soft-question Vincent Russo
źródło
3
Ogólnie w takich pytaniach bardzo przydatne byłoby sprecyzowanie, jaką pracę masz napisać: na przykład mgr, mgr, doktorat, coś jeszcze? W szczególności, czy oczekuje się, że przeprowadzi nowe badania lub „po prostu” uporządkuje istniejącą wiedzę?
Jukka Suomela,
1
Przepraszam, że nie sprecyzowałem, edytowałem to powyżej, aby pokazać, że to dla mojego magistra. O ile mogę stwierdzić, wszystkie tezy muszą wnosić nowe wyniki / badania i nie są jedynie organizacją istniejącej wiedzy. Więc coś w tym zaułku, jeśli masz jakieś sugestie.
Vincent Russo,

Odpowiedzi:

9

Chociaż ogólnie zgadzam się z odpowiedzią Davida Eppsteina (i poparłem ją), pojawiająca się dziedzina automatów, które definiują procesy biologiczne i inne „rzeczy” związane z komputerami, jest dynamicznym obszarem. Późniejsze zatrudnienie nie jest czymś, z czym mogę rozmawiać, ale możesz zainteresować się Artificial Biochemistry autorstwa Luca Cardelli lub Efficient Turing - uniwersalne obliczenia z polimerami DNA Qian i in. Pierwszy artykuł jest ostatnią próbą Cardellego dostarczenia formalnych metod dla procesów biochemicznych; drugi - teoretyczna implementacja DNA maszyny stosowej.

Aaron Sterling
źródło
1
Jeśli chodzi o praktyczność zatrudniania zasług związanych z tematem mojej pracy dyplomowej, nie martwię się zbytnio. Uważam, że te tematy są bardzo interesujące i wolałbym poświęcić swój czas na coś, co mnie pasjonuje, niż na czymś, co sprawi, że będę miał grubszy czek. Powiedziawszy to, podoba mi się idea o tematyce biologicznej. Jestem także wielkim fanem obliczeń kwantowych, ale nie jestem pewien, co naprawdę może oznaczać praca magisterska na temat złożoności kwantowej.
Vincent Russo,
Problemy są również inne i trudniejsze niż w przypadku klasycznej pracy z lat 70.: naturalne problemy obliczeniowe zwykle nie są klasycznymi problemami z analizą łańcuchów, lecz ogólnie są acykliczne. Wyszukaj „gramatyki wykresów obliczeń naturalnych”.
Charles Stewart,
1
Rzeczywiście ciekawy temat. Inna gałąź biokomputerów (z którą byłam zaangażowana) poza przesunięciem nici DNA projektu cząstecz- programming.org zajmuje się aspektem „programowania” domeny biokomputerowej : diku.dk/~neil/blobentcs.pdf . Moim stronniczym zdaniem warto przyjrzeć się :)
svrist
1
@svrist, Dziękujemy bardzo za opublikowanie linku do Hartmann i in. papier. Przeczytam to dzisiaj. Wygląda to na odpowiedź na pytanie, które tutaj zadałem : cstheory.stackexchange.com/questions/114/... więc właśnie zrobiłeś mi dzień. :-)
Aaron Sterling
18

Myślę, że David Eppstein jest zbyt lekceważący w dziedzinie teorii automatów i języków formalnych. Twierdzenie, że „opublikowanie go na konferencjach na najwyższym szczeblu i przekonanie kogoś do zatrudnienia cię po ukończeniu studiów może być problematyczne” wydaje się być tym, co Haldane nazwał twierdzeniem cioci Jobiski: „To fakt, który zna cały świat”.

W rzeczywistości istnieją dobre konferencje (takie jak STACS i ICALP), które rutynowo publikują wyniki w teorii automatów i językach formalnych; organizowane są konferencje (takie jak DLT), które koncentrują się na tym obszarze; jest to bardzo aktywny obszar w Niemczech, Francji i we Włoszech; w okolicy istnieją wielkie otwarte problemy; i znam wielu studentów, którzy nie mieli problemu ze znalezieniem pracy.

Jeffrey Shallit
źródło
1
To uspokajające, ponieważ nie jest zbyt zaskakujące, ponieważ teoria automatów i języki formalne leżą u podstaw wszystkiego, co można sobie wyobrazić w dziedzinie informatyki. Jeśli chodzi o rynek pracy, nie inwestuję w to czasu, ponieważ zależy mi na zarabianiu pieniędzy, robię to, ponieważ jestem pasjonatem tematyki. Dziękuję za sugestie.
Vincent Russo,
1
Do tego czasu, czy są jakieś dobre repozytoria online dla tych otwartych problemów, o których wspomniałeś? Znalazłem kilka tu i tam, ale większość z nich zawiera najbardziej „komercyjne” teoretyczne tematy informatyki. tj. NP? = P itp. Jeszcze raz dziękuję za pomoc.
Vincent Russo,
3
@Captainhampton: Możesz spróbować przejrzeć przebieg konferencji takich jak STACS i ICALP (jak wspomniano w odpowiedzi Jeffreya), aby sprawdzić najnowsze prace i rozwiązywać wynikające z nich problemy. Przy użyciu tej metody często można znaleźć tematy dobrej tezy.
Ryan Williams,
10

Pomoc w pracy magisterskiej jest jednym z powodów, dla których mamy opiekunów dla doktorantów, dlatego powinieneś skonsultować się z opiekunem na ten temat.

Ogólna rada, którą usłyszałem, jest taka, że ​​powinieneś wybrać postępowanie z szeregu ostatnich renomowanych konferencji w dziedzinie, w której chcesz pracować, i rzucić okiem na zawarte w nich dokumenty, aż znajdziesz coś interesującego i przedyskutujesz to z przełożonym, aby sprawdzić, czy to rozsądny temat pracy magisterskiej.

Kaveh
źródło
1
Dzięki za opinie Kaveh. Rozmawiałem tam iz powrotem z moim doradcą, ale ostatecznie decyzja należy do mnie, ponieważ to ja poświęcę większość jego czasu na tematykę. Ciekawe, czy ktoś tutaj miał jakieś dobre doświadczenia licencjackie z tym tematem. Być może coś związanego ze złożonością kwantową, ale „rozmiar zgryzu” wystarczający dla poziomu pracy magisterskiej.
Vincent Russo,
7

Innym owocnym obszarem, o którym jeszcze nie wspomniano, jest związek między teorią automatów a logiką. Wydaje mi się, że ten kierunek badań jest bardziej popularny w Europie niż w Ameryce Północnej. Ponieważ nie pracuję na tym polu, nie mogę zasugerować konkretnego problemu. Ale możesz sprawdzić najnowsze LICS 2010, a także poprzednie najnowsze prace. Te notatki do wykładów z kursu przez Leonida Libkin jest to miłe miejsce, aby rozpocząć.

Dai Le
źródło
4
Jako przykład, badanie zagnieżdżonych języków słów rozpoznawanych przez widoczne automaty wypychające przyciągnęło wiele uwagi w ciągu ostatniej dekady. Jednym z powodów jest to, że jest to dobry model wielu problemów związanych z XML, innym jest to, że model służy do powiązania pracy w kilku różnych obszarach (teoria języka programowania, weryfikacja oprogramowania, współbieżność, logika). Wydaje się, że jest to jeden z tych tematów, które naprawdę przekraczają podział A / B. cis.upenn.edu/~alur/nw.html
András Salamon
6

Teoretyczne studium teorii automatów i języków formalnych jest swego rodzaju konaniem (co oznacza, że ​​prawdopodobnie nadal możesz znaleźć ciekawe problemy badawcze do pracy, ale opublikowanie ich na konferencjach na najwyższym poziomie i przekonanie kogoś do zatrudnienia cię po ukończeniu studiów może być problematyczne) . Uważam jednak, że prowadzone są również interesujące prace nad zastosowaniem formalnej teorii języka do wykrywania zagrożeń internetowych / włamań itp., A obszar ten wydaje się teraz znacznie gorętszy.

Zobacz np

Wagner and Dean, Wykrywanie włamań za pomocą analizy statycznej, IEEE Symp. Bezpieczeństwo i prywatność 2001

Wagner i Soto, Mimicry ataki na systemy wykrywania włamań oparte na hoście, ACM Conf. Bezpieczeństwo komputerów i komunikacji 2002

Giffin, Jha i Miller, Skuteczne wykrywanie intruzów kontekstowych, NDSS 2004

Feng i wsp., Formalizowanie czułości w analizie statycznej do wykrywania włamań, Sympozjum IEEE na temat bezpieczeństwa i prywatności 2004

David Eppstein
źródło
1
Zgadzam się, że brakuje praktyczności na rynku pracy teorii automatów, ale zastosowania teorii są dość liczne, jak wykazaliście. Dziękuję za rekomendacje. Czy są jakieś inne odpowiednie tematy dotyczące automatów, w tym bezpieczeństwo, które możesz polecić? Naprawdę chciałbym zrobić coś z kwantową teorią złożoności, ale wierzę, że może to być nieco ambitne dla projektu magisterskiego (być może doktora).
Vincent Russo,
3
Również David, myślę, że poddajesz się krótkim metodom formalnym stosowanym w weryfikacji. Zwłaszcza w przypadku takich rzeczy jak automaty Buchi pojawiają się różnego rodzaju interesujące pytania. Właśnie odeszli od ziemi STOC / FOCS / SODA.
Suresh Venkat