More decidable instances of Post's correspondence problem: beyond counting |
| |
Authors: | Mirko Rahn |
| |
Affiliation: | Universität Karlsruhe (TH), IAKS Vollmar, D-76128 Karlsruhe, Germany |
| |
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. |
| |
Keywords: | Post correspondence problem Context-free language Decidability Combinatorial problems |
本文献已被 ScienceDirect 等数据库收录! |