首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号