posted on 2015-08-07, 11:18authored byJoel 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 satis es 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/pre x/su x. Finally, an alternative class of mechanisms for
generating periodicity forcing words is developed, resulting in a class of examples which contrast those known already.
Funding
This work was supported by the London Mathematical Society, grant SC7-1112-02.
History
School
Science
Department
Computer Science
Published in
Theoretical Computer Science
Citation
DAY, J.D., REIDENBACH, D. and SCHNEIDER, J.C., 2015. Periodicity forcing words. Theoretical Computer Science, 601, pp. 2-14.
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
2015
Notes
This paper was accepted for publication in the journal Theoretical Computer Science and the definitive published version is available at: http://dx.doi.org/10.1016/j.tcs.2015.08.033