|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (advisor) ; Currie, James (referee) ; Masáková, Zuzana (referee)
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...
|
|
|
Structure of equality sets
Hadravová, Jana ; Holub, Štěpán (advisor) ; Currie, James (referee) ; Masáková, Zuzana (referee)
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...
|
|
|
A polynomial algorithm for the binary PCP
Kuřinová, Petra ; Holub, Štěpán (advisor) ; Růžička, Pavel (referee)
The Post correspondence problem, introduced in 1946 by Emil Post, is an important example of undecidable problem. Therefore PCP figures in pro- ofs of some results in theory of formal languages, matrix theory and other. The decidability of the Post correspondence problem proved Ehrenfeucht, Karhumäki and Rozenberg in the 1980s and Halava, Harju and Hirvensalo in 2002 ended the proof. Eight years later was verified that the solution can be found even in polynomial time. The main goal of this diploma thesis is to describe this algorithm in detail and to implement it in a web application. The thesis also introduces basics of com- binatorics on words and some facts about PCP and produces some interesting examples of instances of PCP. Keywords: Post correspondence problem, generalized Post correspondence problem, binary PCP, polynomial algorithms on words, successors of morphisms 1
|
guest ::
