Název: Rozlišování dvojic slov pomocí konečných automatů
Překlad názvu: Distinguishing pairs of words using finite automata
Autoři: Bilan, Daria ; Koucký, Michal (vedoucí práce) ; Šámal, Robert (oponent)
Typ dokumentu: Diplomové práce
Rok: 2023
Jazyk: eng
Abstrakt: [eng] [cze]
This work considers a fundamental open problem in informatics - distin- guishing two words by a deterministic finite automaton with the smallest pos- sible number of states. We review the existing research, where proven lower and upper bounds in terms of words' lengths differ exponentially. Next, we empirically try two approaches not studied previously: analysis of discerning sets and application of randomly generated automata. We show that the first approach does not help improve the bounds for the main problem, while the random automata could be successful for randomly taken word pairs but not for all of them. A combination of a randomly generated automaton with the best performing already known, though, may decrease an average number of states by several orders of magnitude. We propose several topics for further investigation based on the obtained experimental results. 1 V této práci se zaměřujeme na jeden ze základních otevřených problémů v in- formatice - rozlišování dvou slov pomocí deterministického konečného automatu s co nejmenším počtem stavů. Nejprve představíme existující výzkum, kde se prokázané dolní a horní meze vzhledem k délce slov liší exponenciálně. Následně empiricky zkoušíme dva dosud neprozkoumané přístupy: analýzu rozlišujících množin a použití náhodně generovaných automatů. Ukážeme, že první přístup nepřispívá ke zlepšení mezí pro daný problém, zatímco náhodné automaty mo- hou být úspěšné pro náhodně vybrané páry slov, avšak ne pro všechny. Kom- binace náhodně generovaného automatu s již známým nenáhodným přístupem však pomáhá snížit průměrný počet stavů o několik řádů. Na základě získaných experimentálních výsledků navrhujeme několik témat pro další výzkum. 1
Klíčová slova: Konečné automaty|rozlišování slov|Složitost|Náhodné automaty; Finite automata|Distinguishing words|Complexity|Random automata

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/185008

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-535154


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce