Distinguishing pairs of words using finite automata
| Název práce v češtině: | Rozlišování dvojic slov pomocí konečných automatů |
|---|---|
| Název v anglickém jazyce: | Distinguishing pairs of words using finite automata |
| Klíčová slova: | Konečné automaty|rozlišování slov|Složitost|Náhodné automaty |
| Klíčová slova anglicky: | Finite automata|Distinguishing words|Complexity|Random automata |
| Akademický rok vypsání: | 2022/2023 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | prof. Mgr. Michal Koucký, Ph.D. |
| Řešitel: | Mgr. Daria Bilan - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 03.07.2023 |
| Datum zadání: | 03.07.2023 |
| Datum potvrzení stud. oddělením: | 11.07.2023 |
| Datum a čas obhajoby: | 11.09.2023 09:00 |
| Datum odevzdání elektronické podoby: | 20.07.2023 |
| Datum odevzdání tištěné podoby: | 24.07.2023 |
| Datum proběhlé obhajoby: | 11.09.2023 |
| Oponenti: | doc. Mgr. Robert Šámal, Ph.D. |
| Zásady pro vypracování |
| Cílem práce je zmapovat známé výsledky o rozlišování dvojic řetězců pomocí konečných automatů a získat nové výsledky k tomuto problému.
Problém rozlišování řetězců pomocí konečných automatů byl zaveden Goralčíkem a Koubkem v 1986. Otázkou je, jak velký automat je potřeba na rozlišení libovolné dvojice řetezců délky n. Nehledě na značné úsilí mnohých, nejlepší současná mez na asymptotickou velikost takového automatu je O(n^1/3) (Chase, 2021). Cílem práce je prostudovat současnou literaturu k tomuto problému, zjistit, co se dá říci o tomto problému, a zaměřit se na studium náhodných automatů řešících tento problém. Součástí tak může být experimentální či teoretická studie náhodných automatů pro tento problém. |
| Seznam odborné literatury |
| Goralčík, P., Koubek, V. (1986). On discerning words by automata. In: Kott, L. (eds) Automata, Languages and Programming. ICALP 1986. Lecture Notes in Computer Science, vol 226, pages 116-122.
Z. Chase. Separating words and trace reconstruction. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. pages 21–31, 2021. M. Robson. Separating strings with small automata. Information Processing Letters, 30(4):209–214, 1989. |