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

^*Corresponding author for this work

School of Mathematics and Statistics

Beijing Institute of Technology

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

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.

Original language	English
Pages (from-to)	451-457
Number of pages	7
Journal	RAIRO - Theoretical Informatics and Applications
Volume	46
Issue number	3
DOIs	https://doi.org/10.1051/ita/2012015
Publication status	Published - Jul 2012

Keywords

Semi-Thue system
Theory of computation
Undecidable
ωPCP

Access to Document

10.1051/ita/2012015

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this