Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong; Qinghui Liu

doi:10.1051/ita/2012015

Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong^*, Qinghui Liu

^*此作品的通讯作者

数学学院

Beijing Institute of Technology

科研成果: 期刊稿件 › 文章 › 同行评审

9 引用（Scopus）

摘要

The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231-245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO-Theor. Inf. Appl. 40 (2006) 551-557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju's construction. So we prove that ωPCP is undecidable for domain alphabets of size 8.

源语言	英语
页（从-至）	451-457
页数	7
期刊	RAIRO - Theoretical Informatics and Applications
卷	46
期	3
DOI	https://doi.org/10.1051/ita/2012015
出版状态	已出版 - 7月 2012

访问文件

10.1051/ita/2012015

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{faaa1a72f18f4d45b05900e5cde11f40,

title = "Undecidability of infinite post correspondence problem for instances of size 8",

abstract = "The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231-245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO-Theor. Inf. Appl. 40 (2006) 551-557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju's construction. So we prove that ωPCP is undecidable for domain alphabets of size 8.",

keywords = "Semi-Thue system, Theory of computation, Undecidable, ωPCP",

author = "Jing Dong and Qinghui Liu",

year = "2012",

month = jul,

doi = "10.1051/ita/2012015",

language = "English",

volume = "46",

pages = "451--457",

journal = "RAIRO - Theoretical Informatics and Applications",

issn = "0988-3754",

publisher = "EDP Sciences",

number = "3",

}

TY - JOUR

T1 - Undecidability of infinite post correspondence problem for instances of size 8

AU - Dong, Jing

AU - Liu, Qinghui

PY - 2012/7

Y1 - 2012/7

N2 - The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231-245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO-Theor. Inf. Appl. 40 (2006) 551-557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju's construction. So we prove that ωPCP is undecidable for domain alphabets of size 8.

AB - The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231-245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO-Theor. Inf. Appl. 40 (2006) 551-557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju's construction. So we prove that ωPCP is undecidable for domain alphabets of size 8.

KW - Semi-Thue system

KW - Theory of computation

KW - Undecidable

KW - ωPCP

UR - http://www.scopus.com/inward/record.url?scp=84868702727&partnerID=8YFLogxK

U2 - 10.1051/ita/2012015

DO - 10.1051/ita/2012015

M3 - Article

AN - SCOPUS:84868702727

SN - 0988-3754

VL - 46

SP - 451

EP - 457

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

IS - 3

ER -

Undecidability of infinite post correspondence problem for instances of size 8

摘要

访问文件

其它文件与链接

指纹

引用此