| Issue |
RAIRO-Theor. Inf. Appl.
Volume 40, Number 4, October-December 2006
|
|
|---|---|---|
| Page(s) | 551 - 557 | |
| DOI | https://doi.org/10.1051/ita:2006039 | |
| Published online | 08 November 2006 | |
Undecidability of infinite post correspondence problem for instances of Size 9
Department of Mathematics and TUCS – Turku Centre for Computer
Science, University of Turku, 20014 Turku, Finland;
vesa.halava@utu.fi; harju@utu.fi
Received:
25
January
2005
Accepted:
16
September
2005
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 ω such that h(ω) = g(ω). 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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.