The extended equation of Lyndon and Schützenberger

•The extension of the Lyndon–Schützenberger equation to pseudo-periodic words is considered.•Solutions' pseudo-periodicity completely characterised.•Proofs based on novel combinatorial insights in the structure of pseudo-repetitions. Lyndon and Schützenberger (1962) [3] investigated for which v...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2017-05, Vol.85, p.132-167
Main Authors: Manea, Florin, Müller, Mike, Nowotka, Dirk, Seki, Shinnosuke
Format: Article
Language:English
Subjects:
Combinatorics on words
Lyndon–Schützenberger equation
Pseudoperiodicity
Word equations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•The extension of the Lyndon–Schützenberger equation to pseudo-periodic words is considered.•Solutions' pseudo-periodicity completely characterised.•Proofs based on novel combinatorial insights in the structure of pseudo-repetitions. 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].
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2016.11.003