Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428794 | Information Processing Letters | 2008 | 5 Pages |
Abstract
We present a new technique to decide or reduce instances of Post's correspondence problem. It generalizes balance arguments to a consideration about some special context-free languages which allow the combination with other decision (or reduction) techniques. In spite of its simplicity, the new technique is able to decide more instances than known techniques.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics