Original title: Struktura ekvivalenčních množin
Translated title: Structure of equality sets
Authors: Hadravová, Jana ; Holub, Štěpán (advisor) ; Currie, James (referee) ; Masáková, Zuzana (referee)
Document type: Doctoral theses
Year: 2015
Language: eng
Abstract: [eng] [cze]
Title: Structure of equality sets Author: Jana Hadravová Department: Department of Algebra Supervisor: doc. Mgr. Štěpán Holub, Ph.D., Dept. of Algebra Abstract: Binary equality set of two morphisms g, h : ⌃⇤ ! A⇤ is a set of all words w over two-letter alphabet ⌃ satisfying g(w) = h(w). Elements of this set are called binary equality words. One of the important results of research on binary equality sets is the proof of the fact that each binary equality set is generated by at most two words provided that both morphisms g and h are non-periodic. Moreover, if a binary equality set is generated by exactly two words, then the structure of both generators, and therefore of the whole set, is uniquely given. This work presents the results of our research on the structure of binary equality sets with a single generator. Importantly, these generators can be decomposed into simpler structures. Generators which can not be further decomposed are called simple equality words. First part of the presented work describes the structure of simple equality words and introduces their detailed classification. The main result of the first part is a precise characterisation of su ciently large simple equality words. In the second part, the work describes the iterative process which transforms a general generator of a binary... 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...
Keywords: Binary equality sets; Combinatorics on words; Periodicity forcing words; Post Correspondence Problem; binární ekvivalenční množiny; kombinatorika na slovech; Postův korespondenční problém; slova vynucující periodicitu

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

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


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