Transition Property for α-Power Free Languages with α≥ 2 and k≥ 3 Letters
share
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 Σ_k denote an alphabet with k letters. Let L_k,α denote the α-power free language over the alphabet Σ_k, where α is a rational number or a rational "number with +". If α is a "number with +" then suppose k≥ 3 and α≥ 2. If α is "only" a number then suppose k=3 and α>2 or k>3 and α≥ 2. We show that: If u∈ L_k,α is a right extendable word in L_k,α and v∈ L_k,α is a left extendable word in L_k,α then there is a (transition) word w such that uwv∈ L_k,α. We also show a construction of the word w.
READ FULL TEXT