More decidable instances of Post's correspondence Problem: beyond counting
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. (C) 2007 Elsevier B.V. All rights reserved.
decidability context-free language post correspondence problem combinatorial problems