## 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.

### MSC:

 68R15 Combinatorics on words 68Q42 Grammars and rewriting systems

### Keywords:

non-overlapping words; replacement systems