Article ID Journal Published Year Pages File Type
4951239 Journal of Computer and System Sciences 2017 36 Pages PDF
Abstract
Lyndon and Schützenberger (1962) [3] investigated for which values of ℓ,m, and n, the word-equations uℓ=vmwn have only periodic solutions. Following their result, we determine precisely the values of ℓ,m, and n for which the generalised Lyndon-Schützenberger word equationsu1⋯uℓ=v1⋯vmw1⋯wn, where ui∈{u,θ(u)} for all 1≤i≤ℓ, vj∈{v,θ(v)} for all 1≤j≤m, wk∈{w,θ(w)} for all 1≤k≤n, and θ is an antimorphic involution, have only θ-periodic solutions, i.e., u,v,w∈{t,θ(t)}⁎ for some word t. This answers completely an open problem by Czeizler et al. (2009) [22].
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,