Loughborough University
Browse
Day_Reidenbach_Schneider_Periodicity_forcing_words_Conference_Preprint.pdf (327.48 kB)

Periodicity forcing words

Download (327.48 kB)
conference contribution
posted on 2014-01-23, 12:54 authored by Joel DayJoel Day, Daniel Reidenbach, Johannes C. Schneider
The Dual Post Correspondence Problem asks, for a given word α, if there exists a non-periodic morphism g and an arbitrary morphism h such that g(α) = h(α). Thus α satisfies the Dual PCP if and only if it belongs to a non-trivial equality set. Words which do not satisfy the Dual PCP are called periodicity forcing, and are important to the study of word equations, equality sets and ambiguity of morphisms. In this paper, a 'prime' subset of periodicity forcing words is presented. It is shown that when combined with a particular type of morphism it generates exactly the full set of periodicity forcing words. Furthermore, it is shown that there exist examples of periodicity forcing words which contain any given factor/prefix/suffix. Finally, an alternative class of mechanisms for generating periodicity forcing words is developed, resulting in a class of examples which contrast those known already.

History

School

  • Science

Department

  • Computer Science

Citation

DAY, J.D., REIDENBACH, D. and SCHNEIDER, J.C., 2013. Periodicity forcing words. IN: Karhumäki, J., Lepistö, A.; Zamboni, L. (eds.). Combinatorics on Words: 9th International Conference, WORDS 2013, Turku, Finland, September 16-20, 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): 8079, pp.107-118.

Publisher

© Springer-Verlag Berlin Heidelberg

Version

  • AM (Accepted Manuscript)

Publication date

2013

ISBN

9783642405785;9783642405792

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes in Computer Science (LCNS);8079

Language

  • en