Distinguishing pairs of words using finite automata
| Thesis title in Czech: | Rozlišování dvojic slov pomocí konečných automatů |
|---|---|
| Thesis title in English: | Distinguishing pairs of words using finite automata |
| Key words: | Konečné automaty|rozlišování slov|Složitost|Náhodné automaty |
| English key words: | Finite automata|Distinguishing words|Complexity|Random automata |
| Academic year of topic announcement: | 2022/2023 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. Mgr. Michal Koucký, Ph.D. |
| Author: | Mgr. Daria Bilan - assigned and confirmed by the Study Dept. |
| Date of registration: | 03.07.2023 |
| Date of assignment: | 03.07.2023 |
| Confirmed by Study dept. on: | 11.07.2023 |
| Date and time of defence: | 11.09.2023 09:00 |
| Date of electronic submission: | 20.07.2023 |
| Date of submission of printed version: | 24.07.2023 |
| Date of proceeded defence: | 11.09.2023 |
| Opponents: | doc. Mgr. Robert Šámal, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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. |