Day_Reidenbach_Schneider_IJFCS_DLT13.pdf (325.76 kB)

On the dual post correspondence problem

Download (325.76 kB)
journal contribution
posted on 14.05.2015, 15:05 by Joel DayJoel Day, Daniel ReidenbachDaniel Reidenbach, Johannes C. Schneider
The Dual Post Correspondence Problem asks whether, for a given word α, there exists a pair of distinct morphisms σ,τ, one of which needs to be non-periodic, such that σ(α) = τ(α) is satisfied. This problem is important for the research on equality sets, which are a vital concept in the theory of computation, as it helps to identify words that are in trivial equality sets only. Little is known about the Dual PCP for words α over larger than binary alphabets, especially for so-called ratio-primitive examples. In the present paper, we address this question in a way that simplifies the usual method, which means that we can reduce the intricacy of the word equations involved in dealing with the Dual PCP. Our approach yields large sets of words for which there exists a solution to the Dual PCP as well as examples of words over arbitrary alphabets for which such a solution does not exist.

Funding

This work was supported by the London Mathematical Society, grant SC7-1112-02.

History

School

  • Science

Department

  • Computer Science

Published in

International Journal of Foundations of Computer Science

Volume

25

Issue

8

Pages

1033 - 1048

Citation

DAY, J.D., REIDENBACH, D. and SCHNEIDER, J.C., 2014. On the dual post correspondence problem. International Journal of Foundations of Computer Science, 25 (8), pp. 1033 - 1048.

Publisher

© World Scientific Publishing Co. Pte Ltd

Version

AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2014

Notes

This article was published in the International Journal of Foundations of Computer Science [© World Scientific Publishing Co. Pte Ltd] and the definitive version is available at: http://dx.doi.org/10.1142/S012905411440022X

ISSN

0129-0541

Language

en