Transition Property for [Formula: see text]-Power Free Languages with [Formula: see text] and [Formula: see text] Letters

In 1985, Restivo and Salemi presented a list of five problems concerning power free languages. Problem 4 states: Given [Formula: see text]-power-free words u and v, decide whether there is a transition from u to v. Problem 5 states: Given [Formula: see text]-power-free words u and v, find a transition word w, if it exists. Let [Formula: see text] denote an alphabet with k letters. Let [Formula: see text] denote the [Formula: see text]-power free language over the alphabet [Formula: see text], where [Formula: see text] is a rational number or a rational “number with [Formula: see text]”. If [Formula: see text] is a “number with [Formula: see text]” then suppose [Formula: see text] and [Formula: see text]. If [Formula: see text] is “only” a number then suppose [Formula: see text] and [Formula: see text] or [Formula: see text] and [Formula: see text]. We show that: If [Formula: see text] is a right extendable word in [Formula: see text] and [Formula: see text] is a left extendable word in [Formula: see text] then there is a (transition) word w such that [Formula: see text]. We also show a construction of the word w.