Název: Synchronizace a nespojité zpracování vstupu v přechodových systémech
Překlad názvu: Synchronization and Discontinuous Input Processing in Transition Systems
Autoři: Vorel, Vojtěch ; Čepek, Ondřej (vedoucí práce) ; Otto, Friedrich (oponent) ; Průša, Daniel (oponent)
Typ dokumentu: Disertační práce
Rok: 2018
Jazyk: eng
Abstrakt: [eng] [cze]
Original results in computational and combinatorial theory of reset words in transition systems, road coloring in directed graphs, and discontinuous input processing in formal languages are presented, including strong lower bounds on subset synchronization thresholds, lower bounds on descriptive power of jumping finite automata, and corresponding complexity classifications. Práce shrnuje odpovědi na složitostní a kombinatorické otázky z oblasti synchronizačních slov v přechodových systémech, barvení cesty na orientovaných grafech a nespojitého zpracování vstupu ve formálních jazycích. Výsledky zahrnují především silné dolní odhady synchronizačního prahu v synchronizaci podmnožin, dolní odhady popisné síly skákacích konečných automatů a klasifikaci složitosti příslušných výpočetních úloh.
Klíčová slova: Barvení cesty; Restartovací automaty; Skákající konečné automaty; Synchronizace; Synchronizační slovo; Jumping Finite Automata; Reset Word; Restarting Automata; Road Coloring; Synchronization

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/104303

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


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 > Disertační práce