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
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.

Copyright
© 2012, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2012 National Conference on Information Technology and Computer Science
Series
Advances in Intelligent Systems Research
Publication Date
November 2012
ISBN
978-94-91216-39-8
ISSN
1951-6851
DOI
10.2991/citcs.2012.113How to use a DOI?
Copyright
© 2012, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Jing Dong
PY  - 2012/11
DA  - 2012/11
TI  - The Analysis and Solution of a PCP Instance
BT  - Proceedings of the 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  - 10.2991/citcs.2012.113
ID  - Dong2012/11
ER  -