More decidable instances of Post's correspondence problem: beyond counting
| Autor: | Mirko Rahn |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Reduction (recursion theory)
Theoretical computer science business.industry media_common.quotation_subject Context-free language Information processing Computer Science Applications Theoretical Computer Science Decidability Post correspondence problem Signal Processing Spite Simplicity Artificial intelligence business Correspondence problem Information Systems media_common Mathematics |
| Zdroj: | Information Processing Letters. 106:115-119 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2007.11.002 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect