|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (vedoucí práce) ; Currie, James (oponent) ; Masáková, Zuzana (oponent)
Název práce: Struktura ekvivalenčních množin Autor: Jana Hadravová Katedra: Katedra algebry Vedoucí disertační práce: doc. Mgr. Štěpán Holub, Ph.D., Katedra algebry Abstrakt: Binární ekvivaleční množina dvou homomorfismů g, h : ⌃⇤ ! A⇤ je množina všech slov w nad dvouprkovou abecedou ⌃ splňujících rovnost g(w) = h(w). Prvky této množiny se nazývají binární ekvivalenční slova. Jedním z důležitých výsledků v oblasti ekvivalenčních množin je důkaz toho, že množina generátorů libovolné binární ekvivalenční množiny je maximálně dvou- prvková za podmínky, že jsou oba homomorfismy g, h neperiodické. Pokud je navíc tato množina generována přesně dvěma prvky, je struktura těchto ge- nerátorů, a tím i celé množiny, jednoznačně dána. Předložená práce se zabývá výzkumem struktury binárních ekvivalenčních množin s jedním generátorem. Důležitou vlastností těchto generátorů je možnost je- jich rozkladu na jednodušší struktury. Generátory, které již nelze dále rozložit, se nazývají jednoduchá ekvivalenční slova. První část práce se věnuje struk- tuře jednoduchých ekvivalenčních slov a jejich podrobné klasifikaci. Hlavním výsledkem této části je nalezení přesné struktury jednoduchých ekvivalenčních...
|
|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (vedoucí práce) ; Currie, James (oponent) ; Masáková, Zuzana (oponent)
Název práce: Struktura ekvivalenčních množin Autor: Jana Hadravová Katedra: Katedra algebry Vedoucí disertační práce: doc. Mgr. Štěpán Holub, Ph.D., Katedra algebry Abstrakt: Binární ekvivaleční množina dvou homomorfismů g, h : ⌃⇤ ! A⇤ je množina všech slov w nad dvouprkovou abecedou ⌃ splňujících rovnost g(w) = h(w). Prvky této množiny se nazývají binární ekvivalenční slova. Jedním z důležitých výsledků v oblasti ekvivalenčních množin je důkaz toho, že množina generátorů libovolné binární ekvivalenční množiny je maximálně dvou- prvková za podmínky, že jsou oba homomorfismy g, h neperiodické. Pokud je navíc tato množina generována přesně dvěma prvky, je struktura těchto ge- nerátorů, a tím i celé množiny, jednoznačně dána. Předložená práce se zabývá výzkumem struktury binárních ekvivalenčních množin s jedním generátorem. Důležitou vlastností těchto generátorů je možnost je- jich rozkladu na jednodušší struktury. Generátory, které již nelze dále rozložit, se nazývají jednoduchá ekvivalenční slova. První část práce se věnuje struk- tuře jednoduchých ekvivalenčních slov a jejich podrobné klasifikaci. Hlavním výsledkem této části je nalezení přesné struktury jednoduchých ekvivalenčních...
|
|
|
Polynomiální algoritmus pro binární PCP
Kuřinová, Petra ; Holub, Štěpán (vedoucí práce) ; Růžička, Pavel (oponent)
Postův korespondenční problém, zavedený Emilem Postem v roce 1946, je důležitým příkladem obecně nerozhodnutelného problému. Díky tomu figuruje v důkazech některých výsledků z teorie formálních jazyků, teorie matic a dalších odvětví. Rozhodnutelnost binárního Postova korespondenčího problému dokázali Ehrenfeucht, Karhumäki a Rozenberg v 80. letech a v roce 2002 Halava, Harju a Hirvensalo důkaz dokončili. O osm let později bylo ověřeno, že řešení lze nalézt dokonce v polynomiálním čase. Tato diplomová práce má za hlavní cíl podrobně popsat tento polynomiální algo- ritmus a implementovat jej v rámci webové aplikace. Práce mimo jiné seznamuje se základy kombinatoriky na slovech a různými poznatky o PCP a také předkládá některé zajímavé instance PCP. Klíčová slova: Postův korespondenční problém, zobecněný Postův korespon- denční problém, binární PCP, polynomiální algoritmy na slovech, následníci ho- momorfismů 1
|
host ::
RSS.