Generalised Lyndon-Schützenberger Equations

to full text (938 kB)   ZIP
involved person(s) / institution(s)author :
datePublished :
  • March 2014
size33 S.

We fully characterise the solutions of the generalised Lyndon-Schützenberger word equations \(u_1 \cdots u_\ell = v_1 cdots v_m w_1 \cdots w_n\), where \(u_i \in \{u, \theta(u)\}\) for all \(1 \leq i \leq \ell\), \(v_j \in \{v, \theta(v)\}\) for all \(1 \leq j \leq m\), \(w_k \in \{w, \theta(w)\}\) for all \(1 \leq k ?\leq n\), and \(\theta\) is an antimorphic involution. More precisely, we show for which \(\ell\), \(m\),
and \(n\) such an equation has only \(\theta\)-periodic solutions, i.e., \(u\), \(v\), and \(w\) are in \(\{t, \theta(t)\}^\ast\) for some word \(t\), closing an open problem by Czeizler et al. (2011).
Static URL
IDNumber of report :
  • TR_1403