Original title: Synchronizace a nespojité zpracování vstupu v přechodových systémech
Translated title: Synchronization and Discontinuous Input Processing in Transition Systems
Authors: Vorel, Vojtěch ; Čepek, Ondřej (advisor) ; Otto, Friedrich (referee) ; Průša, Daniel (referee)
Document type: Doctoral theses
Year: 2018
Language: eng
Abstract: [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.
Keywords: Jumping Finite Automata; Reset Word; Restarting Automata; Road Coloring; Synchronization; Barvení cesty; Restartovací automaty; Skákající konečné automaty; Synchronizace; Synchronizační slovo

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/104303

Permalink: http://www.nusl.cz/ntk/nusl-391347


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses