Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951239 | Journal of Computer and System Sciences | 2017 | 36 Pages |
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].
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Florin Manea, Mike Müller, Dirk Nowotka, Shinnosuke Seki,