Article ID Journal Published Year Pages File Type
428794 Information Processing Letters 2008 5 Pages PDF
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