2026-07-26T02:38:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4394 2024-03-06T10:35:01Z ddc:004 open_access

On the Pseudoperiodic Extension of u^l = v^m w^n Manea, Florin Müller, Mike Nowotka, Dirk Word equations Pseudoperiodicity Lyndon-Schützenberger equation We investigate the solution set of the pseudoperiodic extension of the classical Lyndon and Sch\"utzenberger word equations. Consider u_1 ... u_l = v_1 ... v_m w_1 ... w_n, where u_i is in {u, theta(u)} for all 1 <= i <= l, v_j is in {v, theta(v)} for all 1 <= j <= m, w_k is in {w, theta(w)} for all 1 <= k <= n and u, v and w are variables, and theta is an antimorphic involution. A solution is called pseudoperiodic, if u,v,w are in {t, theta(t)}^+ for a word t. [Czeizler et al./I&C/2011] established that for small values of l, m, and n non-periodic solutions exist, and that for large enough values all solutions are pseudoperiodic. However, they leave a gap between those bounds which we close for a number of cases. Namely, we show that for l = 3 and either m,n >= 12 or m,n >= 5 and either m and n are not both even or not all u_i's are equal, all solutions are pseudoperiodic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florin Manea and Mike Müller and Dirk Nowotka 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.475 urn:nbn:de:0030-drops-43948 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.475 eng https://creativecommons.org/licenses/by/3.0/legalcode