The post correspondence problem over a unary alphabet |
| |
| Institution: | Department of Computing Science, University of Alberta Edmonton, Alberta, Canada T6G 2E8;Faculty of Mathematics, University of Twente P.O. Box 217, 7500 AE Enschede, The Netherlands |
| |
| Abstract: | We consider the problem of finding a shortest solution for the Post correspondence problem over a unary alphabet. We show that the complexity of this problem heavily depends on the representation of the input: the problem is NP-complete if the input is given in compact (logarithmic) form, whereas it becomes polynomially solvable if the input is encoded in unary. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
