Transition Property for α-Power Free Languages with α ≥ 2 and k ≥ 3 Letters

摘要

In 1985, Restivo and Salemi presented a list of five problems concerning power free languages. Problem 4 states: Given α-power-free words u and v, decide whether there is a transition from u to v. Problem 5 states: Given α-power-free words u and v, find a transition word w, if it exists. Let Σ_κ denote an alphabet with κ letters. Let L_(κ,α) denote the α-power free language over the alphabet Σ_κ, where α is a rational number or a rational "number with +". If a is α "number with +" then suppose κ ≥ 3 and α ≥ 2. If α is "only" a number then suppose κ = 3 and α > 2 or κ > 3 and α ≥ 2. We show that: If u ∈ L_(κ,α) is a right extendable word in L_(κ,α) and v ∈ L_(κ,α) is a left extendable word in L_(κ,α) then there is a (transition) word w such that uwv ∈ L_(κ,α). We also show a construction of the word w.