On separating sets of words. I. (English) Zbl 1162.68030

The authors consider various combinatorial properties of words related to overlapping. The main results are the following.
They define a word \(w\) to be bordered if there exist two words \(x\), \(y\) (\(x\) non-empty) such that \(w=xyx\). Theorem 3.9 gives a characterization for a non-empty unbordered word \(z\) satisfying \(pzq=uzv\) (for some words \(p,q,u,v\)) and of all other words \(t\) satisfying \(ptq=utv\). Theorem 3.10 classifies the non-empty, unbordered words \(z\) which satisfy \(uvz=zvw\) for some words \(u,v,w\).
Furthermore, the authors define a pair \((u,v)\) of words to be overlapping if there exist words \(x\) and \(y\) such that \(x\) and \(yz\) are non-empty and moreover \(u=yx\), \(v=xz\) hold. Theorem 4.10 then shows that for \(u\), \(v\) distinct words such that both \((u,v)\) and \((v,u)\) are non-overlapping, if furthermore \(dut=xvy\) (for some words \(d,t,x,y\)) then \(dwt\not=xwy\) for any word \(w\).
Finally, the paper also considers replacement systems where any two words appearing on the left-hand side are non-overlapping.


68R15 Combinatorics on words
68Q42 Grammars and rewriting systems