Synchronization, Road Coloring, and Jumps in Finite Automata

• Název práce v češtině: Synchronizace, barvení cesty a skoky v konečných automatech
• Název v anglickém jazyce: Synchronization, Road Coloring, and Jumps in Finite Automata
• Klíčová slova: Synchronizační slovo, Barvení cesty, Skokové automaty
• Klíčová slova anglicky: Reset word, Road coloring, Jumping finite automata
• Akademický rok vypsání: 2014/2015
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: prof. RNDr. Václav Koubek, DrSc.
• Řešitel: Mgr. Vojtěch Vorel, Ph.D. - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 20.01.2015
• Datum zadání: 20.01.2015
• Datum potvrzení stud. oddělením: 14.04.2015
• Datum a čas obhajoby: 04.06.2015 09:00
• Datum odevzdání elektronické podoby: 04.05.2015
• Datum odevzdání tištěné podoby: 05.05.2015
• Datum proběhlé obhajoby: 04.06.2015
• Oponenti: RNDr. František Mráz, CSc.

Zásady pro vypracování

The thesis should bring new theoretical results in the study of reset
words and road coloring in finite automata,
including complexity of computational problems. In addition, it should
focus to properties of language classes
defined recently by jumping finite automata.

Seznam odborné literatury

M. Volkov. Synchronizing automata and the Černý conjecture. In
Language and Automata Theory and Applications, 2008.
A. Trahtman. The road coloring problem. Israel Journal of Mathematics,
172(1), 2009.
P. V. Martyugin. Careful synchronization of partial automata with
restricted alphabets. In Computer Science - Theory and Applications,
2013.
A. Meduna, P. Zemek, Jumping finite automata. Int. J. Found. Comput.
Sci. 23, 2012.