Original title: Polynomiální algoritmus pro binární PCP
Translated title: A polynomial algorithm for the binary PCP
Authors: Kuřinová, Petra ; Holub, Štěpán (advisor) ; Růžička, Pavel (referee)
Document type: Master’s theses
Year: 2013
Language: cze
Abstract: [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
Keywords: binary PCP; generalized Post correspondence problem; polynomial algorithms on words; Post correspondence problem; successors of morphisms; 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

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

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


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