Název: Polynomiální algoritmus pro binární PCP
Překlad názvu: A polynomial algorithm for the binary PCP
Autoři: Kuřinová, Petra ; Holub, Štěpán (vedoucí práce) ; Růžička, Pavel (oponent)
Typ dokumentu: Diplomové práce
Rok: 2013
Jazyk: cze
Abstrakt: [cze] [eng]
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 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
Klíčová slova: binární PCP; následníci homomorfismů; polynomiální algoritmy na slovech; Postův korespondenční problém; zobecněný Postův korespondenční problém; binary PCP; generalized Post correspondence problem; polynomial algorithms on words; Post correspondence problem; successors of morphisms

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/57289

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-326557


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce