EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 57 (2023) RAIRO-Theor. Inf. Appl., 57 (2023) 7 References
Open Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 57, 2023
Article Number 7
Number of page(s) 11
DOI https://doi.org/10.1051/ita/2023008
Published online 18 October 2023
  1. J. Dong and Q. Liu, Undecidability of infinite Post correspondence problem for instances of size 8. RAIRO Theor. Inform. Appl. 46 (2012) 451–457. [CrossRef] [EDP Sciences] [MathSciNet] [Google Scholar]
  2. A. Ehrenfeucht, J. Karhumäki and G. Rozenberg, The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci. 21 (1982) 119–144. [CrossRef] [MathSciNet] [Google Scholar]
  3. M. Ernvall, V. Halava and T. Harju, On the n-permutation Post correspondence problem. Theoret. Comput. Sci. 601 (2015) 15–20. [CrossRef] [MathSciNet] [Google Scholar]
  4. O. Finkel, The exact complexity of the infinite Post correspondence problem. Inform. Process. Lett. 115 (2015) 609–611. [CrossRef] [MathSciNet] [Google Scholar]
  5. V. Halava and T. Harju, Some new results on Post correspondence problem and its modifications. Bull. EATCS 73 (2001) 131–141. [Google Scholar]
  6. V. Halava and T. Harju, New proof for the undecidability of the circular PCP. Acta Inform. 50 (2013) 331–341. [CrossRef] [MathSciNet] [Google Scholar]
  7. V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post correspondence problem. Theoret. Comput. Sci. 276 (2002) 183–204. [CrossRef] [MathSciNet] [Google Scholar]
  8. V. Halava, T. Harju and J. Karhumäki, Decidability of the binary infinite Post correspondence problem. Discrete Appl. Math. 130 (2003) 521–526. [CrossRef] [MathSciNet] [Google Scholar]
  9. V. Halava, T. Harju and E. Sahla, A new proof for undecidability of the bi-infinite Post correspondence problem. Fundam. Inform. 154 (2017) 167–176. [CrossRef] [Google Scholar]
  10. G. Huet and D. Lankford, On the uniform halting problem for term rewriting systems. Rapport Laboria 283, INRIA (1978). [Google Scholar]
  11. T. Neary, Undecidability in binary tag systems and the Post correspondence problem for five pairs of words, in 32nd International Symposium on Theoretical Aspects of Computer Science. Vol. 30 of LIPIcs. Leibniz Int. Proc. Inform.. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2015) 649–661. [Google Scholar]
  12. E.L. Post, A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52 (1946) 264–268. [CrossRef] [Google Scholar]
  13. K. Ruohonen, On some variants of Post’s correspondence problem. Acta Inform. 19 (1983) 357–367. [CrossRef] [MathSciNet] [Google Scholar]
  14. K. Ruohonen, A Note on Permutational Variants of Post’s Correspondence Problem, Vol. 46. Tampere University of Technology, Department of Electr. Eng., Mathematics, Report. Tampere University of Technology (1984). [Google Scholar]

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.