Day_Reidenbach_Schneider_Periodicity_forcing_words_Conference_Preprint.pdf (327.48 kB)
Periodicity forcing words
conference contribution
posted on 2014-01-23, 12:54 authored by Joel DayJoel Day, Daniel Reidenbach, Johannes C. SchneiderThe 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 HeidelbergVersion
- AM (Accepted Manuscript)
Publication date
2013ISBN
9783642405785;9783642405792ISSN
0302-9743eISSN
1611-3349Publisher version
Book series
Lecture Notes in Computer Science (LCNS);8079Language
- en