 |
|
|||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||
 |
||||||||||||||||||||||||||||||||
|
Štěpán Holub: The concept of successor instances in the Post Correspondence ProblemThe Post Correspondence Problem is one of the most important algorithmic problems connected to the combinatorics on words. It is undecidable in general, but decidable in some special cases, namely in the binary case, and also if the the input morphisms are marked. In those decidable cases, a crucial role is played by the concept of "successor instances". We give a general introduction into the idea of successor instances, and then focus on some special properties, which are important in the recent proof that the Binary Post Correspondence Problem is even in P. Falls dieser Text Formeln enthält, die nicht dargestellt werden können, finden Sie hier die dvi- bzw. die pdf-Version. |
HV