EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. Appl.
Volume 40, Number 4, October-December 2006
Page(s) 551 - 557
DOI 10.1051/ita:2006039
Published online 08 November 2006

Theoret. Informatics Appl. 40, 551-557 (2006)
DOI: 10.1051/ita:2006039

Undecidability of infinite post correspondence problem for instances of Size 9

Vesa Halava and Tero Harju

Department of Mathematics and TUCS - Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; vesa.halava@utu.fi; harju@utu.fi


(Received January 25, 2005. Accepted September 16, 2005. Published online 8 November 2006.)

Abstract
In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word $\omega$ such that $h(\omega) = g(\omega)$. This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini (Theory Comput. Syst. 36 (2003) 231-245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable for instances where the morphisms have domains of 9 letters. The proof uses a recent result of Matiyasevich and Sénizergues and a modification of a result of Claus.


Mathematics Subject Classification. 03D35, 03D40, 68R15.

Key words: Infinite Post Correspondence Problem -- undecidability -- word problem -- semi-Thue system.


© EDP Sciences 2006


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.