Teori Automata / Topik Tesis Bahasa Resmi

10

Hai Semua, Saya saat ini mencoba untuk menemukan topik tesis master yang solid yang berkaitan dengan beberapa cabang teori automata atau terkait dengan bahasa formal. Saya mencoba untuk menghasilkan beberapa ide bagus untuk topik yang dapat diterima, sesuatu yang ambisius tetapi sesuatu yang bisa dilakukan pada saat yang bersamaan.

Setiap saran akan sangat dihargai!

ds.algorithms automata-theory fl.formal-languages soft-question Vincent Russo
sumber
3
Secara umum, dalam pertanyaan seperti ini akan sangat berguna untuk menentukan tesis seperti apa yang seharusnya Anda tulis: Misalnya, BSc, MSc, PhD, sesuatu yang lain? Secara khusus, apakah Anda diharapkan melakukan penelitian baru atau "hanya" mengatur pengetahuan yang ada?
Jukka Suomela
1
Saya minta maaf karena tidak menentukan, saya telah mengeditnya di atas untuk menunjukkan itu untuk MSc saya. Sejauh yang saya tahu, semua tesis harus menyumbangkan hasil / penelitian baru dan bukan hanya organisasi pengetahuan yang ada. Jadi selesaikan itu jika Anda punya saran.
Vincent Russo

Jawaban:

9

Sementara saya setuju dengan tanggapan David Eppstein secara umum (dan saya meningkatkannya), bidang automata yang muncul yang mendefinisikan proses biologis dan "hal-hal" komputasi alami lainnya adalah bidang yang dinamis. Dipekerjakan kemudian bukan sesuatu yang bisa saya ajak bicara, tetapi Anda mungkin tertarik untuk melihat Biokimia Buatan oleh Luca Cardelli, atau perhitungan Efisien-Turing-universal dengan polimer DNA oleh Qian et al. Makalah pertama adalah upaya terbaru Cardelli untuk menyediakan metode formal untuk proses biokimia; yang kedua, implementasi DNA teoritis dari mesin stack.

Aaron Sterling
sumber
1
Sejauh kepraktisan mempekerjakan jasa topik skripsi saya, saya tidak terlalu khawatir. Saya menemukan topik-topik ini sangat menarik dan lebih suka mendedikasikan waktu saya sesuatu yang saya sukai daripada sesuatu yang akan membuat saya mendapatkan gaji yang lebih besar. Dengan itu, saya suka ide bertema biologis. Saya juga penggemar berat komputasi kuantum, namun saya tidak yakin apa yang dapat ditimbulkan tesis tingkat master pada kompleksitas kuantum.
Vincent Russo
Masalahnya juga berbeda dan lebih sulit untuk pekerjaan 70-an klasik: masalah komputasi alami cenderung bukan masalah string-parsing klasik, tetapi umumnya lebih dari grafik asiklik. Carilah "grafik tata bahasa komputasi alami".
Charles Stewart
1
Memang topik yang menarik. Cabang lain dari biocomputing (yang saya telah terlibat dengan) di luar perpindahan untai DNA dari proyek molekuler-programming.org telah melihat ke dalam aspek "pemrograman" dari domain biocomputing : diku.dk/~neil/blobentcs.pdf . Menurut pendapat bias saya layak melihat ke :)
svrist
1
@svrist, Terima kasih banyak telah mengirim tautan ke Hartmann et al. kertas. Saya akan membacanya hari ini. Sepertinya jawaban untuk pertanyaan yang saya ajukan di sini: cstheory.stackexchange.com/questions/114/… jadi Anda baru saja membuat hari saya. :-)
Aaron Sterling
18

Saya pikir David Eppstein terlalu meremehkan bidang teori automata dan bahasa formal. Klaim bahwa "mempublikasikannya di konferensi tingkat tinggi dan meyakinkan seseorang untuk mempekerjakan Anda begitu lulus nanti mungkin menjadi masalah" tampaknya yang oleh Haldane disebut Teorema Bibi Jobiska: "Itu fakta yang diketahui seluruh dunia."

Bahkan, ada konferensi yang baik (seperti STACS dan ICALP) yang secara rutin menerbitkan hasil dalam teori automata dan bahasa formal; ada konferensi yang dihadiri banyak orang (seperti DLT) yang berfokus pada area; itu adalah area yang sangat aktif di Jerman, Prancis, dan Italia; ada masalah terbuka yang besar di daerah tersebut; dan saya tahu banyak siswa yang tidak memiliki masalah dalam mendapatkan pekerjaan.

Jeffrey Shallit
sumber
1
Itu meyakinkan, melihat sebagai teori automata dan bahasa formal mendasari semua yang mungkin dilakukan di bidang ilmu komputer itu tidak terlalu mengejutkan juga. Sejauh menyangkut pasar kerja, saya tidak menginvestasikan waktu saya dalam hal ini karena saya peduli untuk menghasilkan uang, saya melakukannya karena saya bersemangat dengan materi pelajaran. Terima kasih atas sarannya.
Vincent Russo
1
Omong-omong, adakah repositori online yang bagus untuk masalah-masalah terbuka yang Anda sebutkan ini? Saya telah menemukan beberapa di sana-sini, tetapi kebanyakan dari mereka menyatakan topik ilmu komputer teoretis yang paling "komersial". yaitu NP? = P dll. Sekali lagi terima kasih atas bantuannya.
Vincent Russo
3
@Captainhampton: Anda mungkin ingin mencoba menelusuri proses konferensi seperti STACS dan ICALP (sebagaimana disebutkan dalam jawaban Jeffrey) untuk mencari pekerjaan terbaru dan membuka masalah yang timbul dari mereka. Topik tesis yang baik sering dapat ditemukan menggunakan metode ini.
Ryan Williams
10

Membantu dengan topik tesis adalah salah satu alasan kami memiliki pengawas untuk mahasiswa pascasarjana, jadi Anda harus berkonsultasi dengan penyelia Anda tentang hal itu.

Nasihat umum yang telah saya dengar adalah bahwa Anda harus memilih proses dari sejumlah konferensi terkemuka baru-baru ini di bidang yang ingin Anda kerjakan dan melihat makalah di dalamnya sampai Anda menemukan sesuatu yang menarik dan membahasnya dengan penyelia Anda untuk melihat apakah ini adalah topik tesis yang masuk akal.

Kaveh
sumber
1
Terima kasih atas umpan balik Kaveh. Saya telah berbicara bolak-balik dengan penasihat saya, tetapi pada akhirnya keputusan ada pada saya karena saya akan menjadi orang yang mendedikasikan sebagian besar waktunya untuk membahas masalah. Jadi hanya ingin tahu apakah ada orang di sini yang memiliki pengalaman tesis yang baik dengan materi pelajaran. Mungkin sesuatu yang berkaitan dengan kompleksitas kuantum tetapi "ukuran gigitan" cukup untuk tingkat tesis master.
Vincent Russo
7

Bidang bermanfaat lainnya yang belum disebutkan di sini adalah hubungan antara teori dan logika automata. Saya kira arah penelitian ini lebih populer adalah Eropa daripada Amerika Utara. Karena saya tidak bekerja di bidang itu, saya tidak dapat menyarankan Anda masalah khusus. Tetapi Anda dapat melihat LICS 2010 terbaru serta yang sebelumnya untuk karya terbaru. The catatan kuliah dari kursus oleh Leonid Libkin adalah tempat yang bagus untuk memulai.

Dai Le
sumber
4
Sebagai contoh, studi bahasa kata bersarang yang diakui oleh automata tampak pushdown telah mengumpulkan banyak perhatian selama dekade terakhir. Salah satu alasannya adalah bahwa ini adalah model yang baik dari banyak masalah yang berkaitan dengan XML, alasan lain adalah bahwa model berfungsi untuk menyatukan kerja di beberapa bidang yang berbeda (teori bahasa pemrograman, verifikasi perangkat lunak, konkurensi, logika). Tampaknya menjadi salah satu topik yang benar-benar melintasi kesenjangan A / B. cis.upenn.edu/~alur/nw.html
András Salamon
6

Studi teoritis tentang teori automata dan bahasa formal adalah semacam hampir mati (artinya, Anda mungkin masih dapat menemukan masalah penelitian yang menarik untuk dikerjakan, tetapi mempublikasikannya di konferensi tingkat atas dan meyakinkan seseorang untuk mempekerjakan Anda setelah lulus mungkin bermasalah) . Namun, saya percaya ada juga pekerjaan menarik yang dilakukan dalam menerapkan teori bahasa formal untuk deteksi ancaman / intrusi internet, dll., Dan area ini tampaknya jauh lebih panas sekarang.

Lihat misalnya

Wagner dan Dean, deteksi intrusi melalui analisis statis, IEEE Symp. Keamanan dan Privasi 2001

Wagner dan Soto, serangan Mimicry pada sistem deteksi intrusi berbasis host, ACM Conf. Keamanan Komputer dan Komunikasi 2002

Giffin, Jha, dan Miller, Deteksi Intrusi Sensitif Konteks-Sensitif, NDSS 2004

Feng et al, Memformalkan Sensitivitas dalam Analisis Statis untuk Deteksi intrusi, Simposium IEEE tentang Keamanan dan Privasi 2004

David Eppstein
sumber
1
Saya setuju bahwa kepraktisan di pasar kerja teori automata masih kurang, namun penerapan teori ini cukup banyak seperti yang Anda tunjukkan. Terima kasih untuk rekomendasinya. Apakah ada topik automata lain yang berlaku yang tidak termasuk keamanan yang dapat Anda rekomendasikan? Saya benar-benar ingin melakukan sesuatu dengan teori kompleksitas kuantum, namun percaya itu mungkin agak ambisius untuk proyek master (mungkin gelar doktoral).
Vincent Russo
3
Juga David, saya pikir Anda memberi sedikit perhatian pada metode formal seperti yang digunakan dalam verifikasi. Terutama ketika melibatkan hal-hal seperti Buchi automata, ada semua jenis pertanyaan menarik. Mereka baru saja pindah dari tanah STOC / FOCS / SODA.
Suresh Venkat