Proceedings of the 2012 National Conference on Information Technology and Computer Science

The Analysis and Solution of a PCP Instance

Authors
Jing Dong
Corresponding Author
Jing Dong
Available Online November 2012.
DOI
https://doi.org/10.2991/citcs.2012.113How to use a DOI?
Keywords
PCP; Post Correspondence Problem; Fibonacci substitution
Abstract
In this paper, we present a heuristic rule for solving some specific PCP instances. We also analyze a PCP instance, and prove that this instance has no finite solution using our heuristic rule. Moreover, we find this instance has a unique infinite solution generated by a Fibonacci substitution.
Open Access
This is an open access article distributed under the CC BY-NC license.

Download article (PDF)

Proceedings
2012 National Conference on Information Technology and Computer Science
Part of series
Advances in Intelligent Systems Research
Publication Date
November 2012
ISBN
978-94-91216-39-8
ISSN
1951-6851
DOI
https://doi.org/10.2991/citcs.2012.113How to use a DOI?
Open Access
This is an open access article distributed under the CC BY-NC license.

Cite this article

TY  - CONF
AU  - Jing Dong
PY  - 2012/11
DA  - 2012/11
TI  - The Analysis and Solution of a PCP Instance
BT  - 2012 National Conference on Information Technology and Computer Science
PB  - Atlantis Press
SP  - 435
EP  - 438
SN  - 1951-6851
UR  - https://doi.org/10.2991/citcs.2012.113
DO  - https://doi.org/10.2991/citcs.2012.113
ID  - Dong2012/11
ER  -