Day_Reidenbach_Schneider_DLT13_final_version.pdf (336.64 kB)
Download file

On the dual post correspondence problem

Download (336.64 kB)
conference contribution
posted on 23.01.2014, 14:36 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. 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.

History

School

  • Science

Department

  • Computer Science

Citation

DAY, J.D., REIDENBACH, D. and SCHNEIDER, J.C., 2013. On the dual post correspondence problem. IN: Béal, M.P. and Carton, O. (eds). Developments in Language Theory: 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 7907, pp.167-178.

Publisher

© Springer-Verlag Berlin Heidelberg

Version

AM (Accepted Manuscript)

Publication date

2013

Notes

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-38771-5_16

ISBN

9783642387708;9783642387715

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes in Computer Science (LCNS);7907

Language

en