Polynomiální algoritmus pro binární PCP

• Thesis title in Czech: Polynomiální algoritmus pro binární PCP
• Thesis title in English: A polynomial algorithm for the binary PCP
• Key words: Postův korespondenční problém, zobecněný Postův korespondenční problém, binární PCP, polynomiální algoritmy na slovech, následníci homomorfismů
• English key words: Post correspondence problem, generalized Post correspondence problem, binary PCP, polynomial algorithms on words, successors of morphisms
• Academic year of topic announcement: 2010/2011
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Algebra (32-KA)
• Supervisor: doc. Mgr. Štěpán Holub, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 12.11.2010
• Date of assignment: 12.11.2010
• Date and time of defence: 01.02.2013 00:00
• Date of electronic submission: 10.12.2012
• Date of submission of printed version: 07.12.2012
• Date of proceeded defence: 01.02.2013
• Opponents: doc. Mgr. Pavel Růžička, Ph.D.

Guidelines

Student se seznámí s Postovým korespondenčním problémem (PCP), zejména s jeho binární verzí a s nedávno popsaným polynomiálním algoritmem pro jeho rozhodování. Tento algoritmus naprogramuje a vytvoří jeho webovou prezentaci. Součástí práce bude i hledání zajímavých instancí problému.

References

Vesa Halava, Štěpán Holub, Binary (Generalized) Post Correspondence Problem is in P
Technical Report 785, TUCS, Sep 2006.
Vesa Halava, Štěpán Holub, Reduction Tree of the Binary Generalized Post Correspondence Problem, to appear in Int. J. Found. Comput. Sci.
Štěpán Holub, Binary morphisms with stable suffix complexity, to appear in Int. J. Found. Comput. Sci.

Preliminary scope of work

PCP je poměrně jednoduše popsatelný algoritmický problém kombinatorické povahy, který je obecně nerozhodnutelný, ale v binárním případě ano (pro velikost 3 až 6 je rozhodnutelnost otevřená). Rozhodnutelnost byla dokázána již v roce 1982, ale v článku jsou chyby a kolem celé věci panuje určitý zmatek. V roce 2003 jsme ukázali, že by rozhodovací proces je polynomiální, díky důkazu jistých teoretických vlastností. Přehledný popis algortimu ale zatím chybí. Problém je také v tom, že většina instancí je rozhodnutelná triviálně, bylo by proto také dobré najít případy, na kterých by se finesy algoritmu vůbec projevily.