inary equality sets are generated by two word



About this version {#about-this-version .unnumbered}
==================

This is a revised version of my paper published (with the same title) in Journal of Algebra 259 (2003), 1–42.

A nucleus of the paper was a part of my Ph.D. thesis supervised by Aleš Drápal (@myphd). The proof was completed during the postdoctoral stay in Turku granted by Turku Centre for Computer Science (TUCS). I am grateful especially to Juhani Karhumäki for making that stay possible. When writing the paper I discussed the topic with Vesa Halava, Tero Harju, Juhani Karhumäki and Juha Kortelainen.

After the publication, I received comments from Elena (Petre) Czeizler, Markku Laine and Václav Flaška. The present version was carefully read by Jiří Sýkora. I am indebted to all of them for their effort, their comments and suggestions.

The most important difficulty discovered was Lemma \[hyper technicke lema\], which does not hold as it stays in the published text. The corrected formulation given in the present version is the one from an early draft of the paper. Before the publication, I decided to use a stronger claim, which is in fact never needed in the paper, and which, as it turned out, is fallacious. Elena pointed out some difficulties in the proof, and Markku found a counterexample, making it clear that the stronger claim cannot be rescued.

The present version was written in October 2007 and August 2012. The material is partly reorganized, terminology is revised and most proofs rewritten. I hope that the text is now substantially more readable than the journal version, which is in some places excessively complicated and discouraging. On the other hand, there are no new discoveries and the overall argument remains the same.

Introduction
============

Binary equality language, i.e., the set on which two binary morphisms agree, is the most simple non-trivial example of an equality language, the notion of which was introduced in @ArtoEquality. Equality languages in general play an important role in formal language theory. For a survey and bibliography see @handbookmorphisms [Section 5].

In the binary case, the morphisms are defined on a monoid generated by two letters. It was for the first time extensively studied by K. Čulík II and J. Karhumäki in @CuKabinary. There, the main claim of our work was conjectured, viz. that a binary equality language is generated by at most two words as soon as at least one of the morphisms is non-periodic (or, equivalently, injective). An important step towards the proof of the conjecture was made in @EKRequality where the following partial characterization was obtained.

\[char\] The equality set of two binary morphisms $g,h:A^*\to \Sigma^*$, where $A=\{a,b\}$, has the following structure:

<span>()</span>

\[char1\] If $g$ and $h$ are periodic, then either ${{\rm Eq}}(g,h)=\{\varepsilon\}$ or $${{\rm Eq}}(g,h)=\{\varepsilon\}\bigcup \{\alpha\in A^+ \  \vert\   \frac{\ {\vert\alpha\vert}_a}{\ {\vert\alpha\vert}_b}=k\}$$ for some $k\geq0$ or $k=\infty$.

\[char2\] If exactly one morphism is periodic, then $${{\rm Eq}}(g,h)=\alpha^*$$ for some word $\alpha\in A^*$.

\[char3\] If both $g$ and $h$ are non-periodic, then either $${{\rm Eq}}(g,h)=\{\alpha, \beta\}^*$$ for some words $\alpha, \beta \in A^*$, or $${{\rm Eq}}(g,h)=(\alpha\gamma^*\beta)^*$$ for some words $\alpha, \beta, \gamma \in A^+$.

The question remained open whether the second possibility of case (\[char3\]), contradicting the conjecture, can actually occur. In the present paper we show that the answer is negative and, moreover, if $\alpha$ and $\beta$ are both nonempty, they start (and end) with different letters. This is formulated in the following main theorem.

\[hlavni veta\] Let $g,h:A^*\to \Sigma^*$ be non-periodic binary morphisms. Let $\alpha$ and $\beta$, with $\alpha\neq\beta$, be nonempty minimal elements of ${{\rm Eq}}(g,h)$. Then $${\mbox{\rm pref}}_1(\alpha)\neq{\mbox{\rm pref}}_1(\beta)\quad\text{and}\quad{\mbox{\rm suff}}_1(\alpha)\neq{\mbox{\rm suff}}_1(\beta)\,.$$

As a trivial consequence we have a solution of the original question.

\[hlavni veta B\] Equality language of two nonperiodic binary morphisms is generated by at most two words.

I am not aware of any way how to prove Theorem \[hlavni veta B\] not using Theorem \[hlavni veta\].

<span>*Remark.*</span> Later, in @unique, it has been shown that the equality sets generated by two words have a precise form. Namely, the following theorem holds true.

Let $g$ and $h$ be distinct nonperiodic binary morphisms such that ${{\rm Eq}}(g,h)$ is generated by two words. Then there is a positive integer $i$ such that $${{\rm Eq}}(g,h)=\{a^ib,\,ba^i\}^*,$$ up to renaming of the letters.

The proof is based on Theorem \[hlavni veta\].

A closely related problem is the size of a test set for binary languages. Indeed, if two morphisms agree on a language, it must be a subset of their equality language. In @EKRequality, it is shown that all binary languages have a three element test set. Our result allows to cut down this bound to two. Let us remark that this improvement is not a simple consequence of the fact that the equality language is generated by two words — the difference in the first (or last) letter is a necessary ingredient.

Preliminaries
=============

In this section, we fix our notation and recall some basic facts. For a reference and unproved claims see @handbookcombinatorics or @oldlot. If $\Sigma$ is an alphabet, then let $\Sigma^*$ be the free monoid, and $\Sigma^+$ the free semigroup generated by $\Sigma$. The empty word is denoted by $\varepsilon$. Any subset of $\Sigma^*$ is called a <span>*language*</span>. Let $A$ denote the two-letter alphabet $\{a,b\}$.

The length of the word is denoted by ${\vertu\vert}$, and ${\vertu\vert}_x$ denotes the number of occurrences of the letter $x$ in $u$. A <span>*prefix*</span> of $u$ is any word $v\in \Sigma^*$ such that there exists a word $v'\in\Sigma^*$ with $u=vv'$. The set of all prefixes of $u$ is denoted by ${\mbox{\rm pref}}(u)$. A prefix $v$ of $u$ is <span>*proper*</span> if $v\neq\varepsilon$ and $v\neq u$. Similarly, <span>*suffix*</span> and <span>*proper suffix*</span> are defined. The set of all suffixes of $u$ is denoted by ${\mbox{\rm suff}}(u)$. The first (the last resp.) letter of a nonempty word $u$ is denoted by ${\mbox{\rm pref}}_1(u)$ (${\mbox{\rm suff}}_1(u)$ resp.). A word $v$ is called a <span>*factor*</span> of $u$ if there exist words $w,w'\in \Sigma^*$ such that $u=w\,v\,w'$.

If $v\in {\mbox{\rm pref}}(u)$ or $u\in {\mbox{\rm pref}}(v)$, then we say that $u$ and $v$ are *prefix-comparable* (or simply *comparable*). The maximal common prefix of words $u$ and $v$ is denoted by $u \wedge v$. If $u$ and $v$ are words, then the maximal <span>*$u$-prefix*</span> of $v$ is the maximal prefix of $v$ that is also a prefix of $u^i$ for some $i$. Analogously, we define the maximal $u$-suffix of $v$. We say that two words are *suffix-comparable* if one is a suffix of the other.

Positive powers $u^n$ of a word are defined as usual, with $u^0=\varepsilon$. We shall sometimes use also negative powers and work with elements of the free group, in order to simplify notation. This should not cause any confusion. For example, if $u$ and $v$ are comparable, then we shall write $u^{-1}v$ even if $v$ is a proper prefix of $u$. In such a case, when $u=vw$, we have $u^{-1}v=w^{-1}$.

We shall define regular languages by regular expressions in a standard way. In particular, the language $\{u^i\ |\ i\geq 1\}$ is denoted by $u^+$ and $u^*=u^+\cup \,\{\varepsilon\}$. We say that $v$ is a prefix (suffix, factor resp.) of $u^+$ if $v$ is a prefix (suffix, factor resp.) of $u^i$ for some $i\geq 1$.

A nonempty word $u$ is called <span>*primitive*</span> if and only if $u=v^n$ implies $u=v$. The <span>*primitive root*</span> of a nonempty word $u$ is the (uniquely given) primitive word $r$ such that $u\in r^+$. Words $u$ and $v$ are called <span>*conjugate*</span> if $u=ww'$ and $v=w'w$ for some words $w$ and $w'$.

If we speak about minimality or maximality of some element, the implicit ordering is the prefix one, i.e., $v\leq u$ if and only if $v\in{\mbox{\rm pref}}(u)$, and $v< u$ if moreover $v\neq u$. (While by the <span>*shortest*</span> word we mean the word with the smallest length.)

Let $u\in \Sigma^+$ be a word $u=l_1l_2\dots l_d$, with $d={\vertu\vert}$ and $l_i\in \Sigma$. Then the <span>*reversal*</span> of the word $u$, denoted by ${\overline{u}\hspace{2pt}}$, is obtained by inverting the order of the letters, viz. $${\overline{u}\hspace{2pt}}=l_dl_{d-1}\dots
l_1\,.$$ Let $g$ be an arbitrary morphism. The <span>*reversal*</span> of $g$ is the morphism denoted by ${\overline{g}\hspace{2pt}}$, which has the same range and domain as $g$, and is defined by $${\overline{g}\hspace{2pt}}(x)={\overline{g(x)}\hspace{2pt}},$$ for each $x\in \Sigma$. Note that in general ${\overline{g}\hspace{2pt}}(u)$ does not equal to $g({\overline{u}\hspace{2pt}})$ nor to ${\overline{g(u)}\hspace{2pt}}$. Instead $${\overline{g}\hspace{2pt}}({\overline{u}\hspace{2pt}})={\overline{g(u)}\hspace{2pt}}.$$ All concepts and reasonings regarding prefixes are valid analogously for suffixes, reversals considered. We shall often use the fact.

A morphism $g$ defined on $\Sigma$ is called <span>*erasing*</span> if $g(x)$ is empty for some $x\in \Sigma$. A morphism $g$ is <span>*periodic*</span> if there is a word $t$ such that $g(x)\in t^*$, for all words $x$ (or, equivalently, all letters $x$). Note that a binary morphism is periodic as soon as it is erasing.

Let $S=T^+$ be a subsemigroup of $\Sigma^+$ generated by a set $T$. The <span>*rank*</span> of $T$ is the cardinality of the minimal set generating $S$. We can write $$\mbox{\rm rank}(T)=\mbox{\rm rank}(S)=\mbox{\rm Card}(S \setminus S\cdot S)\,.$$ By the rank of a monoid $M$ we mean the rank of the semigroup $M\setminus \{\epsilon\}$.

It is a well known fact that for each set $M\subset \Sigma^+$ there exists the smallest free subsemigroup of $\Sigma^+$ containing $M$ and called its <span>*free hull*</span>. A set generating a free semigroup is called a *code*. If any two distinct elements of a code are neither prefix nor suffix comparable, the set is called a *bifix code*.

The <span>*equality set*</span> of two morphisms $g,h:\Delta^*\to \Sigma^*$ is defined by $${{\rm Eq}}(g,h)=\{u\in \Delta^*\ |\ g(u)=h(u)\}\,.$$ It is easy to verify that the set ${{\rm Eq}}(g,h)$ is a free submonoid of $\Delta^*$ generated by the set of its minimal elements $${{\rm eq}}(g,h)={{\rm Eq}}(g,h)\setminus ({{\rm Eq}}(g,h)\setminus \{\varepsilon\})^2\setminus\{\varepsilon\}\,.$$ Note that ${{\rm eq}}(g,h)$ is a bifix code.

Let $g:A^*\to \Sigma^*$ be a nonperiodic binary morphism. By $z_g$ we denote the maximal common prefix of $g(ab)$ and $g(ba)$, i.e. $$z_g=g(ab)\wedge g(ba)\,.$$ Since $g$ is nonperiodic, we have ${\vertz_g\vert}<{\vertg(a)\vert}+{\vertg(b)\vert}$ by Lemma \[prim\] below. If ${\mbox{\rm pref}}_1(g(a))\neq{\mbox{\rm pref}}_1(g(b))$, i.e. $z_g=\varepsilon$, we say that $g$ is <span>*marked*</span>.

Similarly we define ${\underline{z}}_g$ as the maximal common suffix of $g(ab)$ and $g(ba)$. Note that $${\underline{z}}_g={\overline{{\overline{g(ab)}\hspace{2pt}}\wedge {\overline{g(ba)}\hspace{2pt}}}\hspace{2pt}}={\overline{z_{{\overline{g}\hspace{2pt}}}}\hspace{2pt}}$$ and ${\underline{z}}_g=\varepsilon$ is equivalent to ${\overline{g}\hspace{2pt}}$ being marked.

Cartesian product $\Delta^*\times \Delta^*$ is the set of ordered pairs $(u,v)$ of words. It can be seen as a monoid with operation of catenation defined by $(u,v)(u',v')=(uu',vv')$, with the unit $(\varepsilon, \varepsilon)$. Such a monoid is obviously not free, it is even not isomorphic to a submonoid of a free monoid.

Let $g,h :\Delta^*\to \Sigma^*$ be two morphisms. The subset of $\Delta^*\times \Delta^*$ denoted by ${\mathbb C}(g,h)$ and defined by $${\mathbb C}(g,h)=\{(u,v)\ |\ g(u)=h(v)\}$$ will be called the <span>*coincidence set*</span> of morphisms $g$ and $h$. It is generated by the set $${\mathbf c}(g,h)={\mathbb C}(g,h)\setminus ({\mathbb C}(g,h)\setminus \{(\varepsilon,\varepsilon)\})^2\setminus \{(\varepsilon,\varepsilon)\}\,.$$ Any pair $(u,v)\in {\mathbb C}(g,h)$ can be uniquely factorized into minimal pairs $(u_i,v_i)$ satisfying $g(u_i)=h(v_i)$. This is formulated in the following lemma.

\[freely\] Let $g$ and $h$ be non-erasing morphisms. Then ${\mathbb C}(g,h)$ is, as a submonoid of $\Delta^*\times \Delta^*$, freely generated by ${\mathbf c}(g,h)$. Moreover, the set ${\mathbf c}(g,h)$ is a bifix code.

Note that $(u,u)$ is an element of ${\mathbb C}(g,h)$ for each $u\in {{\rm Eq}}(g,h)$, and ${{\rm Eq}}(g,h)$ is given uniquely by ${\mathbb C}(g,h)$ as $${{\rm Eq}}(g,h)=\{u \ |\ (u,u)\in {\mathbb C}(g,h)\}\,.$$

We present several combinatorial lemmas for future (often implicit) reference. Following three lemmas are part of the folklore.

\[prim\] The words $u$ and $v$ commute if and only if they have the same primitive root.

\[Periodicity Lemma\] Let $u^+$ and $v^+$ have a common prefix of length ${\vertu\vert}+{\vertv\vert}$. Then the words $u$ and $v$ commute.

We shall often use the following lemma. It is based on the well known fact that a primitive word $t$ cannot satisfy equality $tt=utv$, with $u$ and $v$ nonempty.

\[factor\]

<span>()</span>

\[factor0\] Let $ww=uwv$. Then $u$, $v$ and $w$ commute.

\[factor3\] Let $uw$ be a prefix of $w^+$. Then $u$ and $w$ commute.

\[factor1\] Let $sw$ be a factor of $w^+$. Then $s$ is a suffix of $w^+$.

\[factor3a\] Let $uw$ be a suffix of $w^+$ and let $w$ be a prefix of $uw$. Then $u$ and $w$ commute.

\[factor4\] Let $u_1$, $u_2$, $w$, $w' \in\Sigma^+$ be words such that $w'$ and $w$ are conjugate, ${\vertu_1\vert}\leq{\vertu_2\vert}$, and the words $u_1w'$, $u_2w'$ are prefixes of $w^{+}$. Then $u_1$ is a suffix of $u_2$ and $u_2u_1^{-1}$ commutes with $w$.

One more lemma, which is easy to prove:

\[gprefix\] Let $g:A^*\to A^*$ be a marked morphism and let $u,v\in A^*$. Then $g(u\wedge v)=g(u)\wedge g(v)$.

The following nice lemma is a key fact about binary morphisms.

\[prefix\] Let $X=\{x,y\}\subseteq \Sigma^+$ be a nonperiodic set (i.e. $xy\neq yx$). Let $u\in xX^*$, $v\in yX^*$ be words such that ${\vertu\vert}, {\vertv\vert} \geq {\vertxy\wedge yx\vert}$. Then $u\wedge v = xy\wedge yx$.

The proof is not difficult (see @handbookcombinatorics, p. 348). The lemma immediately implies that for a nonperiodic binary morphism $h$ and an arbitrary word $u\in A^+$ long enough, the word $z_h$ is a prefix of $h(u)$ and the $({\vertz_h\vert}+1)$-th letter of $h(u)$ indicates the first letter of $u$. For any $u,v\in A^*$ we have $$\begin{aligned}
z_h=h(au)z_h \wedge h(bv)z_h. \label{vsudypritomnyprefix}\end{aligned}$$ It is now easy to see that the morphism ${h_{{\text{\tiny\bf m}}}}$ such that $$\begin{aligned}
{h_{{\text{\tiny\bf m}}}}(u)=z_h^{-1}h(u)z_h, \label{marked definition}\end{aligned}$$ $u\in A$, is well defined. Moreover, it is marked, and the equality (\[marked definition\]) holds for any $u\in A^*$. We shall call it the <span>*marked version*</span> of $h$.

<span>**N.B.**</span> The case $g=h$ is trivial. Throughout the paper we shall implicitly suppose $g\neq h$.

Principal morphisms {#principal}
===================

In this section we show that at least one of the morphisms $g$ and $h$ can be supposed to be marked. As we shall see, this will make our research more convenient. The goal is achieved by choosing a suitable target alphabet.

We say that an (unordered) pair of binary morphisms $g,h: A^*\to \Sigma^*$ is <span>*principal*</span> if the target alphabet $\Sigma$ generates the free hull of the set $\{g(a),g(b),h(a),h(b)\}$.

The previous definition reflects the use of the term "principal morphism" in literature (see for example @oldlot, p. 170). The advantages of principal morphisms stem from the following important property.

Let $X$ be a finite subset of $\Sigma^*$ and let $Y$ be the minimal generating set of the free hull of $X$. Then for each element $y\in
Y$ there is a word $x\in X$ such that $y$ is a prefix (suffix resp.) of $x$.

For the proof see @defaut, Lemma 3.1. For our purpose, note the following immediate corollary.

\[free hull\] Let $X$ be a finite subset of $\Sigma^*$ such that $\Sigma$ is the base of the free hull of $X$. Then $$\Sigma=\{{\mbox{\rm pref}}_1(u)\ |\ u\in X\}=\{{\mbox{\rm suff}}_1(u)\ |\ u\in X\}.$$

It is quite intuitive that choosing the minimal generating set of the free hull as the target alphabet has no influence on the coincidence set of the morphisms. The following lemma is formulated for binary morphisms, but it can be trivially extended to any domain alphabet.

\[principalni abeceda\] Let $g_1$, $h_1$ be morphisms $A^*\to \Sigma^*$. Then there is a principal pair of morphisms $g$, $h$ such that $$\begin{aligned}
{\mathbb C}(g,h)&={\mathbb C}(g_1,h_1).\end{aligned}$$ Moreover, if $g_1$ $h_1$, ${\overline{g_1}\hspace{2pt}}$, ${\overline{h_1}\hspace{2pt}}$ resp. is marked, then such is also $g$ $h$, ${\overline{g}\hspace{2pt}}$, ${\overline{h}\hspace{2pt}}$ resp..

Let $F\subset \Sigma^*$ be the free hull o the set $\{g_1(a),g_1(b),h_1(a),h_1(b)\}$ and let $C$ be an alphabet whose cardinality equals the rank of $F$. Then $C^*$ and $F$ are isomorphic since they are both free monoids of the same rank; let $\varphi: C^*\to F$ be an isomorphism. Define morphisms $g, h: A^*\to C^*$ by $$\begin{aligned}
    g&=\varphi^{-1}\circ g_1, & h&=\varphi^{-1}\circ h_1.\end{aligned}$$ $$\begin{tikzpicture}[>=angle 45, shorten >=0.5mm, shorten <=1mm]
\node (A) at (0,0) {$A^*$};
\node (F) at (2.5,1) {$F$};
\node (C) at (2.5,-1) {$C^*$};
\draw[->] (A)--(F) node [above, sloped,midway]{{\small $g_1,h_1$}};
\draw[->] (A)--(C) node [above,sloped, midway]{{\small $g,h$}};
\draw[->, transform canvas={xshift=-0.9ex}] (C)--(F) node [left, midway]{{\small$\varphi$}};
\draw[->, transform canvas={xshift=0.9ex}] (F)--(C) node [right, midway]{{\small$\varphi^{-1}$}};
\end{tikzpicture}$$ Then $(g,h)$ is a principal pair of morphisms, the above diagram commutes, and ${\mathbb C}(g,h)={\mathbb C}(g_1,h_1)$. The rest is obvious.

The previous lemma shows that we can always, without loss of generality, suppose that the pair we work with is principal. We can now prove that this brings about markedness of one of the morphisms.

\[principalni markovanost\] Let $g$, $h$ be nonperiodic principal morphisms, with ${{\rm eq}}(g,h)$ nonempty. Then at least one of the morphisms $g$, $h$ is marked, and at least one of the morphisms ${\overline{g}\hspace{2pt}}$, ${\overline{h}\hspace{2pt}}$ is marked.

Suppose that none of the morphisms is marked, therefore $$\begin{aligned}
{\mbox{\rm pref}}_1(g(a))&={\mbox{\rm pref}}_1(g(b)),& {\mbox{\rm pref}}_1(h(a))={\mbox{\rm pref}}_1(h(b)).\end{aligned}$$ Let $x$ be a first letter of a word $u\in{{\rm Eq}}(g,h)$. Then $$\begin{aligned}
{\mbox{\rm pref}}_1(g(x))&={\mbox{\rm pref}}_1(h(x)),\end{aligned}$$ and Corollary \[free hull\] implies that the morphisms are periodic, a contradiction.

Obviously, the morphisms ${\overline{g}\hspace{2pt}}$, ${\overline{h}\hspace{2pt}}$ are also principal, since the concept of the free hull is preserved under the reversal symmetry. This concludes the proof.

The block structure of the coincidence set {#blocks}
==========================================

In this section, we study the structure of the equality set of nonperiodic morphisms and their relation to the coincidence set. The previous section justifies why we shall always suppose that $g$ is marked.

Let $u,v\in \Sigma^*$ be words such that $g(u)$ and $h(v)$ are comparable. Then the word $h(v)^{-1}g(v)$ is called an *overflow* (the overflow may be a "negative" word if $g(v)$ is a prefix of $h(v)$). Following lemmas show that the possibility to lengthen the words $u$, $v$ to words $u'$, $v'$ such that $g(u')=h(v')$ is very restricted. Namely, the overflow $z_h$ is the only one admitting two different continuations.

\[critical\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked. Let $u,v\in A^*$ be words such that $g(u)$ and $h(v)$ are comparable and let $$g(u)\neq h(v)z_h\,.$$ Let $u_1,u_2,v_1,v_2\in A^+$ be words such that $$\begin{aligned}
g(uu_1)&=h(vv_1), & g(uu_2)&=h(vv_2).\end{aligned}$$ Then

-   ${\mbox{\rm pref}}_1(u_1)={\mbox{\rm pref}}_1(u_2)$, if $|g(u)|-|h(v)|<|z_h|$;

-   ${\mbox{\rm pref}}_1(v_1)={\mbox{\rm pref}}_1(v_2)$, if $|g(u)|-|h(v)|>|z_h|$.

If $u_1$, $u_2$, $v_1$ and $v_2$ satisfy the conditions of the lemma, then the same conditions are satisfied also by the words $u_1uu_1$, $u_2uu_2$, $v_1vv_1$ and $v_2vv_2$ resp. Hence we can suppose that each of the words $u_1,u_2,v_1,v_2$ is longer than $z_h$. Consider three cases.

<span>1.</span>

First suppose that ${\vertg(u)\vert}<{\verth(v)\vert}+{\vertz_h\vert}$. By (\[vsudypritomnyprefix\]), $h(v)z_h$ is a prefix of both $h(vv_1)$ and $h(vv_2)$ and $$\begin{aligned}
{\mbox{\rm pref}}_1(g(u_1))={\mbox{\rm pref}}_1(g(u_2))={\mbox{\rm pref}}_1(g(u)^{-1}h(v)z_h)=x.\end{aligned}$$ Since $g$ is a marked morphism, this implies that ${\mbox{\rm pref}}_1(u_1)={\mbox{\rm pref}}_1(u_2)$. $$\begin{tikzpicture}
 \horA{0}{90}{${g(u)}$}
 \dolA{0}{60}{${h(v)}$}
 \dolseda{90}{98}{$x$}
 \doldashA{60}{115}{}
 \doludolbra{60}{115}{$z_h$}
\end{tikzpicture}$$

<span>2.</span>

Suppose on the other hand that ${\vertg(u)\vert}>{\verth(v)\vert}+{\vertz_h\vert}$. Then $h(v_1)$, $h(v_2)$ have the common prefix longer than $z_h$ and ${\mbox{\rm pref}}_1(v_1)={\mbox{\rm pref}}_1(v_2)$ is determined by the letter $x={\mbox{\rm pref}}_1((h(v)z_h)^{-1}g(u))$. $$\begin{tikzpicture}
 \horseda{125}{133}{$x$}
 \horA{0}{150}{${g(u)}$}
 \dolA{0}{75}{${h(v)}$}
 \doldashA{75}{125}{$z_h$}
\end{tikzpicture}$$

<span>3.</span>

If ${\vertg(u)\vert}={\verth(v)\vert}+{\vertz_h\vert}$, then, clearly, $g(u)=h(v)z_h$. $$\begin{tikzpicture}
 \horA{0}{170}{${g(u)}$}
 \dolA{0}{120}{${h(v)}$}
 \doldashA{120}{170}{$z_h$}
\end{tikzpicture}$$

Previous lemma yields the following property.

\[cor1\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked. Let $(c,d)$ and $(c',d')$ be distinct elements of ${\mathbb C}(g,h)$, and suppose that $c$ and $c'$ are not comparable. Put $$\begin{aligned}
u&=c\wedge c',& v&=d\wedge d'.\end{aligned}$$ Then $$g(u)=h(v)z_h.$$

We have $c=uu_1$ and $c'=uu_2$ where $u_1,u_2\in A^+$ and ${\mbox{\rm pref}}_1(u_1)\neq {\mbox{\rm pref}}_1(u_2)$.

If $d$ and $d'$ are not comparable, then $d=vv_1$ and $d'=vv_2$ with $v_1,v_2\in A^+$ and ${\mbox{\rm pref}}_1(v_1)\neq {\mbox{\rm pref}}_1(v_2)$, and the claim follows from Lemma \[critical\].

If $d$ and $d'$ are comparable, then ${\vertg(u)\vert}-{\verth(v)\vert}<0\leq {\vertz_h\vert}$. Since $$\begin{aligned}
g(uu_1c)&=h(vv_1d), & g(uu_2c')&=h(vv_2d')\end{aligned}$$ with $u_1c, u_2c', v_1d, v_1d'\in A^+$, Lemma \[critical\] yields a contradiction with ${\mbox{\rm pref}}_1(u_1)\neq {\mbox{\rm pref}}_1(u_2)$.

The previous corollary does not hold without the condition that $c$ and $c'$ are not comparable. Consider morphisms $$\begin{aligned}
g(a)&=a, & g(b)&=b,\\
h(a)&=a, & h(b)&=aab. \end{aligned}$$ Then $(c,d)=(a,a)$, $(c',d')=(aab,b)$, $z_h=aa$, and $$g(c\wedge c')=g(a)=a\neq aa= h(\varepsilon)z_h=h(d\wedge d')z_h.$$

The ground for the characterization of the coincidence set is the following lemma.

\[ef\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked. Let the words $e,f\in A^+$ satisfy following conditions:

<span>()</span>

\[ef1\] $z_hg(e)=h(f)z_h$

\[ef2\] The words $e$, $f$ are minimal, i.e.: If $u\leq e$, $v\leq f$ and $z_hg(u)=h(v)z_h$, then either $u=v=\varepsilon$ or $u=e$ and $v=f$.

Then, given the first letter of $e$ or the first letter of $f$, the words $e$ and $f$ are determined uniquely.

Suppose $e$, $f$ and $e'$, $f'$ satisfy (\[ef1\]) and (\[ef2\]), and ${\mbox{\rm pref}}_1(e)={\mbox{\rm pref}}_1(e')$. Put $c=e\wedge e'$, $d=f\wedge
f'$. Since $g$ is a marked morphism, we have $$\begin{aligned}
\label{pr1}
z_hg(e)\wedge z_hg(e')=z_hg(c)\end{aligned}$$ by Lemma \[gprefix\]. From (\[vsudypritomnyprefix\]) we deduce $$\begin{aligned}
\label{pr2}
h(f)z_h\wedge h(f')z_h=h(d)z_h.\end{aligned}$$ Since $z_hg(e)=h(f)z_h$ and $z_hg(e')=h(f')z_h$, the equalities (\[pr1\]), (\[pr2\]) yield $$\begin{aligned}
z_hg(c)=h(d)z_h.\end{aligned}$$ Since $c$ is nonempty, we deduce from (\[ef2\]) that $c=e=e'$ and $d=f=f'$. Similarly if ${\mbox{\rm pref}}_1(f)={\mbox{\rm pref}}_1(f')$.

This implies the following lemma.

\[coref\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked.

<span>()</span>

The rank of ${\mathbb C}(g,{h_{{\text{\tiny\bf m}}}})$ is at most two.

If the rank of ${\mathbb C}(g,{h_{{\text{\tiny\bf m}}}})$ is two and ${\mathbf c}(g,{h_{{\text{\tiny\bf m}}}})=\{(e,f),(e',f')\}$, then $$\begin{aligned}
{\mbox{\rm pref}}_1(e)&\neq{\mbox{\rm pref}}_1(e')\\
{\mbox{\rm pref}}_1(f)&\neq{\mbox{\rm pref}}_1(f').\end{aligned}$$

Recall that ${h_{{\text{\tiny\bf m}}}}(u)=z_h^{-1}h(u)z_h$ to see that $${\mathbb C}(g,{h_{{\text{\tiny\bf m}}}})=\{(u,v)\in A^*\times A^*\ \vert\ z_hg(u)=h(v)z_h\}\,.$$ The rest is a consequence of Lemma \[ef\].

Note that $(e,f)\in{\mathbf c}(g,{h_{{\text{\tiny\bf m}}}})$ is just another formulation of the fact that $e$, $f$ are minimal words satisfying $z_hg(e)=h(f)z_h$, which are exactly conditions of Lemma \[ef\]. The pairs $(e,f)$ and $(e',f')$ are often called *blocks* of $g$ and $h$.

The question on the structure of the equality set ${{\rm Eq}}(g,h)$ can be seen as a special case of the above considerations. If conditions $$\begin{aligned}
u&=v,  & u_1&=v_1, & u_2&=v_2, &c&=d,  &c'&=d', &e&=f, &e'&=f',\end{aligned}$$ are added, then we get the following modifications of Lemma \[critical\], Lemma \[cor1\], Lemma \[ef\] and Lemma \[coref\] with analogous proofs, which we omit.

\[critical revisited\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked. Let $u\in A^*$ be a word such that $g(u)$ and $h(u)$ are comparable, and $$g(u)\neq h(u)z_h\,.$$ Let $u_1,u_2\in A^+$ be words such that $$\begin{aligned}
g(uu_1)&=h(uu_1),\\ g(uu_2)&=h(uu_2).\end{aligned}$$ Then ${\mbox{\rm pref}}_1(u_1)={\mbox{\rm pref}}_1(u_2)$.

\[cor1 revisited\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked. Let $c$ and $c'$ be incomparable elements of ${{\rm Eq}}(g,h)$. Put $u=c\wedge c'$. Then $$g(u)=h(u)z_h.$$

\[ef revisited\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked. Let the word $e\in A^+$ satisfy following conditions:

<span>()</span>

$z_hg(e)=h(e)z_h$

The word $e$ is minimal, i.e.: If $e_1$ is a prefix of $e$ and $z_hg(e_1)= h(e_1)z_h$, then $e_1=\varepsilon$ or $e_1=e$.

Then the word $e$ is determined uniquely by its first letter.

\[coref revisited\] Let $g$ and $h$ be binary morphisms, and let $g$ be marked.

<span>()</span>

The rank of ${{\rm Eq}}(g,{h_{{\text{\tiny\bf m}}}})$ is at most two.

If the rank of ${{\rm Eq}}(g,{h_{{\text{\tiny\bf m}}}})$ is two and ${{\rm eq}}(g,{h_{{\text{\tiny\bf m}}}})=\{e,e'\}$, then $$\begin{aligned}
{\mbox{\rm pref}}_1(e)&\neq{\mbox{\rm pref}}_1(e').\end{aligned}$$

Note that the previous lemma proves Theorem \[hlavni veta\] for morphisms, which are marked from both sides. In the rest of the paper we show that this is essentially the only situation in which the equality set can have rank greater than one.

Marked morphisms are in general much easier to deal with. That's why it is convenient to work with principal pairs, where one of the morphisms, say $g$, is marked. Moreover, it is always possible to use the marked version ${h_{{\text{\tiny\bf m}}}}$ instead of $h$ to get a marked pair, and thus a better insight into the coincidence set of $g$ and $h$.

The block structure of the coincidence set of marked morphisms leads to an important concept of *successor morphisms* introduced first in @EKRPCP. Consider marked morphisms $g$ and $h$ such that ${\mathbf c}(g,h)$ consists of two blocks $(e,f)$ and $(e',f')$. Let $w$ be an element of ${{\rm Eq}}(g,h)$. The equality $g(w)=h(w)$ can be uniquely split into a sequence of blocks. This means that $w$ is an element of $\{e,e'\}^+$, and in the same time an element of $\{f,f'\}^+$. It is now natural to define the successor morphisms $(g_1,h_1)$ by $$\label{jdeto} \begin{cases}  g_1(a)=e,\\
                   g_1(b)=e',
    \end{cases}
    \begin{cases}  h_1(a)=f,\\
                    h_1(b)=f'\,,
    \end{cases}$$ and to formulate the previous considerations by the following lemma.

\[seq1\] Let $g, h$ be marked morphisms such that $${\mathbf c}(g,h)=\{(e, f),\, (e', f')\}.$$ Then the morphisms $g_1$, $h_1$ defined by are marked. If $w\in {{\rm Eq}}(g,h)$, then there is a unique word $w_1\in {{\rm Eq}}(g_1,h_1)$ such that $$\begin{aligned}
g_1(w_1)&=h_1(w_1)=w.\end{aligned}$$

The morphisms $g_1$ and $h_1$ are marked by Lemma \[coref\]. The existence and uniqueness of the word $w_1$ follows from $(w,w)\in {\mathbb C}(g,h)$, and from Lemma \[freely\].

The counterexample and its structure {#counterexample section}
====================================

We now have all necessary ingredients for the proof of our main claim, Theorem \[hlavni veta\]. The course of the prove will be essentially by contradiction. We shall assume that there exists a counterexample to the claim, and gradually show that such an assumption is contradictory.

We first formulate what is understood as a counterexample.

\[counterexample\] We say that a pair of morphisms $(g,h)$ is a <span>*counterexample*</span> if

<span>()</span>

\[defa\] The rank of ${{\rm Eq}}(g,h)$ is at least two;

\[defb\] $g$ is marked and $h$ is not marked;

\[delky\] ${\vertg(a)\vert}>{\verth(a)\vert}$ and ${\vertg(b)\vert}<{\verth(b)\vert}$.

The third condition takes advantage of the symmetry of letters $a$ and $b$. Note that the strict inequalities do not harm generality, since ${\vertg(a)\vert}={\verth(a)\vert}$ or ${\vertg(b)\vert}={\verth(b)\vert}$ would imply $g=h$. Since the letters $a$ and $b$ are not interchangeable anymore, we shall sometimes need the morphism $\pi$ defined by $\pi(a)=b$ and $\pi(b)=a$.

The following lemma yields basic information about the structure of the equality set of a counterexample.

\[counterexample structure\] Let $(g,h)$ be a counterexample. Then there exist nonempty words $\sigma$, $\nu_a$ and $\nu_b$ such that $|\sigma|_a\geq 1$, $$\begin{aligned}
{\mbox{\rm pref}}_1(\nu_a)&=a, & {\mbox{\rm pref}}_1(\nu_b)&=b,\end{aligned}$$ the words $\sigma\nu_a$, $\sigma\nu_b$ are two distinct elements of ${{\rm eq}}(g,h)$ and $$\begin{aligned}
 g(\sigma)&=h(\sigma)z_h, \label{zacatek}\\
 z_hg(\nu_a)&=h(\nu_a),\label{prostredeka}\\
 z_hg(\nu_b)&=h(\nu_b)\label{prostredekb}.\end{aligned}$$ $$\begin{tikzpicture}
  \preghA{10}
  \ramec{0}{130} 
  \stredA{70}{40}
  \uzel{20}{$\sigma$}
  \uzel{100}{${\nu_l}$}
  \nadpisA{40}{70}{$z_h$} 
\end{tikzpicture}$$

Let $u$ and $v$ be two distinct elements of ${{\rm eq}}(g,h)$. Note that $u$ and $v$ are not comparable, and put $\sigma=u\wedge v$, $u_1=\sigma^{-1}u$ and $v_1=\sigma^{-1}$. Clearly, ${\mbox{\rm pref}}_1(u_1)\neq{\mbox{\rm pref}}_1(v_1)$ and the choice of $\nu_a$ and $\nu_b$ is now obvious. The equalities (\[zacatek\]), (\[prostredeka\]) and (\[prostredekb\]) are yielded by Lemma \[cor1 revisited\], and $|\sigma|_a\geq 1$ follows from $|g(b)|<|h(b)|$.

The equalities , and are of a special importance in the proof. They represent two points, where the structure of a counterexample is well defined, and which therefore yield information for a combinatorial analysis.

The following lemma makes sure that the counterexample defined above deserves its name.

\[uprava\] Let $g_1$ and $h_1$ be nonperiodic binary morphisms such that ${{\rm eq}}(g_1,h_1)$ contains two elements $\alpha$ and $\beta$ with the same first letter. Then there is a counterexample $(g,h)$ such that ${{\rm Eq}}(g,h)={{\rm Eq}}(g_1,h_1)$.

Moreover, if ${\overline{g_1}\hspace{2pt}}$ (${\overline{h_1}\hspace{2pt}}$ resp.) is marked, then also ${\overline{g}\hspace{2pt}}$ (${\overline{h}\hspace{2pt}}$ resp.) is marked.

Lemma \[principalni abeceda\] yields principal morphisms $g$ and $h$ such that ${{\rm Eq}}(g,h)={{\rm Eq}}(g_1,h_1)$. By Lemma \[principalni markovanost\] and by the symmetry of $g$ and $h$, we can suppose that $g$ is marked. Similarly, by the symmetry of $a$ and $b$, we can suppose that the condition of Definition \[counterexample\] is satisfied. In order to see that $(g,h)$ is a counterexample, it remains to show that $h$ is not marked. If $h$ is marked, then both morphisms are marked, and ${\mbox{\rm pref}}_1(\alpha)\neq {\mbox{\rm pref}}_1(\beta)$ by Lemma \[coref revisited\], contrary to the assumption.

Markedness of reversals is conserved by Lemma \[principalni abeceda\].

The further strategy is to show that there is no counterexample. We shall divide the investigation into several stages.

When $z_h$ commutes {#zh commutes}
===================

In this section we investigate two special situations, in which $z_h$ commutes with one of the image words. We show that those situations lead to a contradiction. We start with a technical lemma, which will be the core of the proof. In the original version of this paper the claim had the following strong form:

\[hyper technicke lema stare\] <span>*Let $g,h:A^*\to A^*$ be two marked morphisms. Let $u$, $u'$, $v$ and $v'\in A^*$ be words, and $s$, $r$, $q$ positive integers such that $$\begin{aligned}
 g(a^sbu)&=h(a^sbu'), &
 g(a^{r}bv)&=h(a^{q}bv').\end{aligned}$$ Then $s=r=q$.*</span>

However, as Markku Laine pointed out by constructing an example, this claim does not hold. The example is as follows.

Let $$\begin{aligned}
g(a)&=a^2b^2, & h(a)&=a, \\
g(b)&=b, & h(b)&=b^2.\end{aligned}$$ Then $$g(a^2b^2)=h(a^2ba^2bb)=a^2b^2a^2b^4,$$ and $$g(ab^2)=h(a^2b^2)=a^2b^4.$$

We therefore present a bit weaker version, which fits the purpose of this paper.

\[hyper technicke lema\] Let $g,h:A^*\to A^*$ be two marked morphisms. Let $u$ and $v\in A^*$ be words, and $s$, $r$, $q$ positive integers such that $$\begin{aligned}
 g(a^sbu)&=h(a^sbu),\label{nekk} \\
 g(a^{r}bv)&=h(a^{q}bv).\end{aligned}$$ Then $s=r=q$.

Recall that we suppose $g\neq h$. (Obviously, only $r=q$ is forced if $g=h$.) Let $g$ and $h$ be morphisms satisfying assumptions, and suppose that $s=r=q$ does not hold. Assume, moreover, that $g$ and $h$ are chosen such that the length of $a^sbu$ is the smallest possible. We show that $a^sbu$ can be shortened, and hence obtain a contradiction.

We first prove that $g(a)$ and $h(a)$ do not commute. Suppose for a while that ${\vertg(a)\vert}>{\verth(a)\vert}$, and that $t$ is the common primitive root of $g(a)$ and $h(a)$. From , we deduce that $h(b)$ is comparable with $h(a^s)^{-1}g(a^s)$, which is an element of $t^+$. That is a contradiction with $h$ being marked. Similarly if ${\vertg(a)\vert}<{\verth(a)\vert}$. (Clearly, $g(a)=h(a)$ implies $g=h$.)

Let us continue the proof of the lemma. Lemma \[gprefix\] applied once to $g$ and once to $h$ gives $$\begin{aligned}
\label{weq}
 g(a^{s}bu\wedge a^{r}bv) &=g(a^{s}bu)\wedge g(a^{r}bv)=h(a^{s}bu)\wedge h(a^{q}bv)=h(a^{s}bu\wedge a^{q}bv).\end{aligned}$$

<span>1.</span>

If $s\neq r$ and $s\neq q$, then (\[weq\]) yields $$g(a^i)=h(a^j),$$ with $i=\min(s,r)$, $j=\min(s,q)$. Therefore the words $g(a)$ and $h(a)$ commute, a contradiction.

<span>2.</span>

Suppose next, by symmetry, $s=r$ and $s\neq
q$. Put $m=\min(s,q)$. Equality (\[weq\]) implies $$\begin{aligned}
\label{1712}
g(a^sbw)=h(a^m),\end{aligned}$$ where $w=u\wedge v$.

The set ${\mathbb C}(g,h)$ contains elements $(a^sbu,a^sbu)$ and $(a^sbw,a^m)$, whence the rank of ${\mathbb C}(g,h)$ is two. Let $(e,f)$ and $(e',f')$ be the blocks of $g$ and $h$, and let $g_1$, $h_1$ be their successor morphisms defined by .

By symmetry, suppose that ${\mbox{\rm pref}}_1(f)=a$. Equality (\[1712\]) implies that there is a positive integer $p$ such that $f=a^{p}.$ Since $g(a)$ and $h(a)$ do not commute, we deduce that $e\notin
a^+$ and thus ${\verte\vert}>s$. Since $a^sbu$ and $a^qbv$ are elements of $\{f,f'\}^*$, both $s$ and $q$ are multiples of $p$. Put $$\begin{aligned}
s_1&=\frac s p,&q_1&=\frac q p,\end{aligned}$$ and define words $u_1$ and $v_1$ by $$\begin{aligned}
g_{1}(u_{1})&=a^sbu, & h_{1}(u_{1})&=a^sbu, \\
g_{1}(v_{1})&=a^{s}bv, & h_{1}(v_{1})&=a^{q}bv.
  \end{aligned}$$ Since $f=a^p$, the words $u_1$ and $v_1$ can be factorized as $$\begin{aligned}
u_1&=a^{s_1}bu_2, &  v_1&=a^{q_1}bv_2,\end{aligned}$$ with $u_2,v_2\in A^*$. Therefore $$\begin{aligned}
g_{1}(a^{s_1}bu_2)&=h_{1}(a^{s_1}bu_2)=a^sbu,\\
g_1(a^{q_1}bv_2)&=h_1(a^{s_1}bv_2)=a^sbv.\end{aligned}$$ Inequality $s\neq q$ implies $s_1\neq q_1$, and ${\verte\vert}>s$ yields ${\verta^{s_1}bu_2\vert}<{\verta^sbu\vert}$. This completes the proof.

The following two claims exploit the previous lemma. The words $\sigma$, $\nu_a$ and $\nu_b$ are as in Lemma \[counterexample structure\].

\[nekomutuje s b\] There is no counterexample such that $z_h$ commutes with $g(b)$ and ${\mbox{\rm pref}}_1(\sigma)=b$.

Suppose that $(g,h)$ is such a counterexample, and let $t$ be the common primitive root of $z_h$ and $g(b)$. Let $b^{\ell}$ be the maximal $b$-prefix of $\sigma\nu_a$ and $b^k$ be the maximal $b$-prefix of $\nu_b\sigma$. Then $g(b)^\ell$ is the maximal $t$-prefix of $g(\sigma\nu_a)$ and $z_hg(b)^k$ is the maximal $t$-prefix of $z_hg(\nu_b\sigma)$.

Suppose that $h(b)$ commutes with $g(b)$. Since ${\verth(b)\vert}>{\vertg(b)\vert}$, the equality $g(\sigma\nu_a)=h(\sigma\nu_a)$ implies that $g(a)$ is comparable with $g(b)^{-\ell}h(b)^\ell$, a contradiction with $g$ being marked. Therefore $h(b)$ and $g(b)$ do not commute.

By Lemma \[factor\], the maximal $t$-prefix of $h(b)z_h$ is shorter than ${\verth(b)t\vert}$. This implies, by , that all words $h(bu)$ long enough have the same maximal $t$-prefix. In particular, the maximal $t$-prefix of $h(\sigma\nu_a)$ is the same as the maximal $t$-prefix of $h(\nu_b\sigma)$. From $h(\sigma\nu_a)=g(\sigma\nu_a)$ and $h(\nu_b\sigma)z_h=z_hg(\nu_b\sigma)$ we deduce that $g(b)^\ell=z_hg(b)^k$ and $k\neq \ell$.

Put $\sigma'=b^{-\ell}\sigma$ and note that $\sigma'$ is nonempty since $\sigma$ contains the letter $a$. Then $$\begin{aligned}
z_hg(b^k\sigma')&=h(b^\ell\sigma')z_h,& z_hg(\nu_b\sigma)&=h(\nu_b\sigma)z_h,\end{aligned}$$ and Lemma \[hyper technicke lema\], applied to morphisms ${h_{{\text{\tiny\bf m}}}}\circ\pi$ and $g\circ\pi$, yields a contradiction.

\[nekomutuje s a\] There is no counterexample such that ${\mbox{\rm pref}}_1(\sigma)=a$, $z_h$ commutes with $h(a)$, and the common primitive root of $z_h$ and $h(a)$ is a suffix of $g(a)$.

As in the previous proof, suppose that $(g,h)$ satisfies assumptions of the claim and let $t$ be the common primitive root of $z_h$ and $h(a)$. Let $a^{\,\ell}$ be the maximal $a$-prefix of $\sigma\nu_b$, and $a^k$ be the maximal $a$-prefix of $\nu_a\sigma$.

First, suppose that $g(a)$ commutes with $h(a)$ and $z_h$. Since $g$ is marked, the maximal $t$-prefix of $z_hg(\nu_a\sigma)$ is $z_hg(a)^k$. From , we deduce that the word $z_h$ is the maximal $t$-prefix of $h(bu)z_h$ for any $u$. Hence the maximal $t$-prefix of $h(\nu_a\sigma)z_h$ is $h(a)^kz_h$. The equality $z_hg(\nu_a\sigma)=h(\nu_a\sigma)z_h$ now yields $z_hg(a)^k=h(a)^kz_h$, a contradiction with ${\vertg(a)\vert}>{\verth(a)\vert}$. Therefore $g(a)$ and $h(a)$ do not commute.

Since, by assumption, $t$ is a suffix of $g(a)$, Lemma \[factor\] implies that the maximal $t$-prefix of $g(\sigma\nu_b)=h(\sigma\nu_b)$ is equal to the maximal $t$-prefix of $g(a)$. Using as above, we deduce from that this maximal $t$-prefix is equal to $h(a)^\ell z_h$. In this case, the equality $z_hg(\nu_a\sigma)=h(\nu_a\sigma)z_h$ implies $z_hh(a)^\ell z_h=h(a)^kz_h$ whence $z_h=h(a)^{k-\ell}$.

For $\sigma'=a^{-\ell}\sigma$ we obtain $$\begin{aligned}
z_hg(a^\ell\sigma')&=h(a^{k}\sigma')z_h, & z_hg(\nu_a\sigma)&=h(\nu_a\sigma)z_h.\end{aligned}$$ Since $g(a)$ and $h(a)$ do not commute, we deduce that $\sigma \notin a^+$, whence ${\mbox{\rm pref}}_1(\sigma')=b$ and morphisms ${h_{{\text{\tiny\bf m}}}}$, $g$ satisfy assumptions of Lemma \[hyper technicke lema\], a contradiction.

Case: ${\overline{g}\hspace{2pt}}$ is not marked {#g not marked}
================================================

In this section we deal with the situation when ${\overline{g}\hspace{2pt}}$ is not marked. Note that then ${\overline{h}\hspace{2pt}}$is marked by Lemma \[principalni markovanost\], and verify that $({\overline{h}\hspace{2pt}}\circ \pi,{\overline{g}\hspace{2pt}}\circ \pi)$ is also a counterexample. Recall that $\pi$ exchanges letters $a$ and $b$, and it is applied in order to satisfy the condition of Definition \[counterexample\]. This allows to suppose $$\begin{aligned}
 {\vert{\underline{z}}_g\vert}\geq{\vertz_h\vert} \label{delsi zetko}.
 \end{aligned}$$ More precisely, if ${\vert{\underline{z}}_g\vert}<{\vertz_h\vert}$, then we consider $({\overline{h}\hspace{2pt}}\circ \pi,{\overline{g}\hspace{2pt}}\circ \pi)$, instead of $(g,h)$.

The equality (\[vsudypritomnyprefix\]) applied to reversals implies that ${\underline{z}}_g$ is a suffix of any $g(u)$ long enough. Especially, $$\begin{aligned}
&\text{${\underline{z}}_g$ is a suffix of $g(a)^+$}, \label{vsudypritomnysuffixA}\\
&\text{${\underline{z}}_g$ is a suffix of $g(b)^+$}. \label{vsudypritomnysuffixB}\end{aligned}$$ Since $z_h$ is a suffix of $g(\sigma)$, which is suffix comparable with ${\underline{z}}_g$, we deduce from that $$\begin{aligned}
 \label{zhsufzg}
  z_h\in{\mbox{\rm suff}}({\underline{z}}_g).
 \end{aligned}$$ $$\begin{tikzpicture}
\preghA{10}
\jensigma{80}{55}
\hordashA{35}{80}{{\scriptsize ${\underline{z}}_g$}}
\uzel{25}{$\sigma$}
\podpisA{55}{80}{$z_h$}
\end{tikzpicture}$$ The following claim excludes the situation of this section.

\[spor zg non-empty\] There is no counterexample with ${\overline{g}\hspace{2pt}}$ not marked.

Suppose that $(g,h)$ is such a counterexample.

<span>1.</span>

Suppose first ${\mbox{\rm pref}}_1(\sigma)=a$. The equality $g(\sigma)=h(\sigma)z_h$ yields $h(a)\in {\mbox{\rm pref}}(g(a))$, and $z_hg(\nu_a)=h(\nu_a)$ implies that $h(a)z_h$ is a prefix of $z_hg(a)$. Thus $z_hh(a)=h(a)z_h$.

Let $t$ be the common primitive root of $h(a)$ and $z_h$. From we deduce that $t$ is a suffix of ${\underline{z}}_g$, and together with ${\vertg(a)\vert}>{\verth(a)\vert}\geq{\vertt\vert}$ yields that $t$ is a suffix of $g(a)$. This is a contradiction with Claim \[nekomutuje s a\].

<span>2.</span>

Suppose then that ${\mbox{\rm pref}}_1(\sigma)=b$. From and (\[zhsufzg\]) we deduce that $z_hg(b)$ is a suffix of $g(b)^+$. Equalities $g(\sigma)=h(\sigma)z_h$ and $z_hg(\nu_b)=h(\nu_b)$ imply that $g(b)$ is a prefix of $h(b)$, and that $h(b)$ is comparable with $z_hg(b)$ respectively. Therefore $g(b)$ is a prefix of $z_hg(b)$, and Lemma \[factor\] yields that $g(b)$ and $z_h$ commute, a contradiction with Claim \[nekomutuje s b\].

Case: ${\overline{h}\hspace{2pt}}$ is not marked {#h not marked}
================================================

In this subsection we consider the situation when ${\overline{g}\hspace{2pt}}$ is marked and ${\overline{h}\hspace{2pt}}$ is not. We shall not exclude this case directly. Instead we reduce it to the case when both ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked.

To accomplish this plan we first we need a description of possible counterexample structure that is more precise than Lemma \[counterexample structure\].

\[presna struktura\] Let $(g,h)$ be a counterexample. Then one of the following possibilities takes place.

<span>()</span>

\[presna struktura1\] There exist words $\sigma, \mu_a,
\mu_b\in A^+$, and $\tau\in A^*$ such that $$\begin{aligned}
{{\rm eq}}(g,h)&=\{\sigma\mu_a\tau,\,\sigma\mu_b\tau\},\end{aligned}$$ where $$\begin{aligned}
z_hg(\mu_a){\underline{z}}_h&=h(\mu_a),& g(\sigma)&=h(\sigma)z_h,\\
z_hg(\mu_b){\underline{z}}_h&=h(\mu_b),& g(\tau)&={\underline{z}}_h h(\tau),\\\end{aligned}$$ and $$\begin{aligned}
{\mbox{\rm pref}}_1(\mu_a)&=a, & {\mbox{\rm pref}}_1(\mu_b)&=b, & {\mbox{\rm suff}}_1(\mu_a)&\neq{\mbox{\rm suff}}_1(\mu_b)\,.\end{aligned}$$ $$\begin{tikzpicture}
\preghA{10}
\ramec{0}{170}
\stredA{70}{40} \stredA{130}{150}
\uzel{20}{$\sigma$} \uzel{100}{$\mu_x$} \uzel{160}{$\tau$}
\podpisA{40}{70}{$z_h$} \podpisA{130}{150}{${\underline{z}}_h$}
\end{tikzpicture}$$

\[presna struktura2\] There exist words $\zeta, \mu, \rho, \eta\in A^+$ such that $${{\rm eq}}(g,h)=\zeta(\rho\mu)^*\rho\eta=\zeta\rho(\mu\rho)^*\eta,$$ and $$\begin{aligned}
g(\zeta){\underline{z}}_h&=h(\zeta),& z_hg(\mu){\underline{z}}_h&=h(\mu),& {\mbox{\rm pref}}_1(\mu)&\neq{\mbox{\rm pref}}_1(\eta), \\
g(\rho)&={\underline{z}}_h h(\rho)z_h, &z_hg(\eta)&=h(\eta), & {\mbox{\rm suff}}_1(\mu)&\neq{\mbox{\rm suff}}_1(\zeta).\end{aligned}$$ $$\begin{tikzpicture}
\preghA{15}
\ramec{-5}{245}
\stredA{20}{40} \stredA{90}{60} \stredA{150}{170} \stredA{220}{190}
\uzel{8}{$\zeta$} \uzel{50}{$\rho$} \uzel{120}{$\mu$} \uzel{180}{$\rho$}  \uzel{233}{$\eta$}
\podpisA{20}{40}{${\underline{z}}_h$} \podpisA{60}{90}{$z_h$} \podpisA{150}{170}{${\underline{z}}_h$} \podpisA{190}{220}{$z_h$}
\end{tikzpicture}$$

Let $\alpha$ and $\beta$ be two shortest elements of ${{\rm eq}}(g,h)$. Put $\sigma=\alpha \wedge \beta$, and similarly let $\tau$ be the longest common suffix of $\alpha$ and $\beta$. By Lemma \[cor1 revisited\], applied first to $g$ and $h$, and then to ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$, we have $$\begin{aligned}
g(\sigma)&=h(\sigma)z_h, \label{alfa}\\
g(\tau)&={\underline{z}}_hh(\tau)\,. \end{aligned}$$ Denote by $v_0$ and $v_1$ the words $\sigma^{-1}\alpha$ and $\sigma^{-1}\beta$. Clearly, ${\mbox{\rm pref}}_1(v_0)\neq {\mbox{\rm pref}}_1(v_1)$.

<span>1.</span>

First suppose that $v_0$ and $v_1$ are not suffix-comparable. Then with a suitable choice of $i,j\in \{0,1\}$ we have $v_i=\mu_a\tau$, $v_j=\mu_b\tau$, and ${\mbox{\rm pref}}_1(\mu_\ell)=\ell$ for both $\ell\in A$.

Therefore $\{\sigma\mu_a\tau,\sigma\mu_b\tau\}=\{\alpha,\beta\}$. We show that $\sigma$ is the unique prefix of $\alpha$ ($\beta$ resp.) satisfying .

Suppose first that $\sigma_1\sigma_2=\sigma$ and $g(\sigma_1)=h(\sigma_1)z_h$. Then it is easy to see that also $\sigma_1v_i\in {{\rm Eq}}(g,h)$, $i=0,1$, a contradiction with $\alpha$ and $\beta$ being the shortest elements of ${{\rm eq}}(g,h)$.

Let then $v_i=w_1w_2$, for some $i\in \{0,1\}$, and $g(\sigma w_1)=h(\sigma w_1)z_h$. Then $\sigma w_2$ is an element of ${{\rm Eq}}(g,h)$, which is shorter than $\sigma v_i$. Since $\alpha$ and $\beta$ are the shortest elements of ${{\rm eq}}(g,h)$, it remains that $\sigma w_2=\sigma v_{1-i}$. But then $v_0$ and $v_1$ are suffix-comparable, a contradiction.

We still have to show that the set $\{\alpha,\beta\}$ generates whole ${{\rm Eq}}(g,h)$. Suppose that $w$ is an element of ${{\rm Eq}}(g,h)$ such that neither $\alpha$, nor $\beta$ is a prefix of $w$, and consider words $w_i=w\wedge \sigma v_i$, $i=0,1$. Lemma \[cor1 revisited\] implies that $g(w_i)=h(w_i)z_h$, for both $i=0,1$. It is easy to deduce that $w_0$ and $w_1$ cannot be both equal to $\sigma$, a contradiction with the previous paragraph. Consequently, we have the case (A).

<span>2.</span>

Suppose now, by symmetry, that $v_1=uv_0$. Then $z_hg(u)=h(u)z_h$ and $\sigma u^* v_0$ is a subset of ${{\rm Eq}}(g,h)$. Moreover, $\sigma$ and $\sigma u$ are the only prefixes of $\sigma u v_0$ satisfying . The proof is similar as above: any other prefix satisfying allows to drop a part of the word, which contradicts the minimality of $\alpha$ and $\beta$. We omit details. This, in particular, implies that $u$ is not a suffix of $\sigma$.

We show that $\sigma u^* v_0$ generates the whole equality set. Suppose the contrary, and let $w$ be the shortest element of ${{\rm eq}}(g,h)$ that is not in $\sigma u^* v_0$. As above, the words $w_0=w \wedge \sigma v_0$ and $w_1=w\wedge \sigma uv_0$ satisfy $g(w_i)=h(w_i)z_h$, $i=0,1$. Therefore $w_0=\sigma$, by the previous paragraph. From ${\mbox{\rm pref}}_1(u)\neq {\mbox{\rm pref}}_1(v_0)$, one obtains that $w_1$ is strictly longer than $\sigma$, which implies $w_1=\sigma u$. Therefore $w=\sigma u w'$, for some $w'$. Hence $\sigma w'$ is an element of ${{\rm eq}}(g,h)$ shorter than $w$, and thus an element of $\sigma u^* v_0$. Therefore $w'\in u^*v_0$ and $w\in\sigma u^* v_0$, a contradiction.

We have seen that $u$ is not a suffix of $\sigma$. Also $\sigma$ cannot be a suffix of $u$, otherwise $\sigma u\sigma^{-1}\in {{\rm Eq}}(g,h)$ will contradict the minimality of $\alpha$ and $\beta$. We can therefore define $\rho$ as the longest common suffix of $u$ and $\sigma$. The word $\rho$ is not empty since $z_h$ is a suffix of both $g(u)$ and $g(\sigma)$, and ${\overline{g}\hspace{2pt}}$ is marked. Denote, $\eta=v_0$, $\zeta=\sigma\rho^{-1}$ and $\mu=u\rho^{-1}$.

Note that the word $\tau=\rho\eta$ is the longest common suffix of $\alpha$ and $\beta$. Lemma \[cor1 revisited\] applied to $({\overline{g}\hspace{2pt}}, {\overline{h}\hspace{2pt}})$ yields $g(\rho\eta)={\underline{z}}_h h(\rho\eta)$. The verification of all claims in case (B) is now straightforward.

Note that the previous lemma proves, in particular, Theorem \[char\].

The following lemma allows to suppose that both ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked, which was the task of this section.

\[koncove zh prazdne\] Let $(g,h)$ be a counterexample. Then there exists also a counterexample $(g_1,h_1)$ such that both ${\overline{g_1}\hspace{2pt}}$ and ${\overline{h_1}\hspace{2pt}}$ are marked.

Suppose that $(g,h)$ is a counterexample. Then ${\overline{g}\hspace{2pt}}$ is marked by Claim \[spor zg non-empty\]. Suppose that ${\underline{z}}_{h}\neq \varepsilon$ and define $g_1$ and $h_1$ by $$\begin{aligned}
 g_1(u)&=g(u), & h_1(u)&={\underline{z}}_{h}h(u)({\underline{z}}_{h})^{-1}.
 \end{aligned}$$ It is not difficult to see that the morphism $h_1$ is well defined, it is not marked while ${\overline{h_1}\hspace{2pt}}$ is marked. It remains to show that ${{\rm Eq}}(g_1,h_1)$ has rank at least two. This is a consequence of the characterization presented in Lemma \[presna struktura\]. (We shall use its notation.)

<span>1.</span>

If the case (\[presna struktura1\]) of Lemma \[presna struktura\] takes place, then $$\{\tau\sigma\mu_a,\,\tau\sigma\mu_b\}\subset {{\rm Eq}}(g_1,h_1)\,.$$ $$\begin{tikzpicture}
\ramec{0}{180}
\preghA{10}
\stredA{110}{60}
\uzel{30}{$\tau\sigma$} \uzel{145}{$\mu_x$}
\podpisA{60}{110}{$z_{h_1}={\underline{z}}_{h} z_{h}$}
\end{tikzpicture}$$

<span>2.</span>

If, on the other hand, we have the case (\[presna struktura2\]) of the Lemma \[presna struktura\], then $$\{\rho\mu,\,\rho\eta\zeta\}\subset {{\rm Eq}}(g_1,h_1)\,.$$ $$\begin{tikzpicture}
\ramec{0}{130}
\preghA{10}
\stredA{65}{15}
\uzel{87}{$\mu$} \uzel{8}{$\rho$}
\podpisA{15}{65}{$z_{h_1}={\underline{z}}_{h} z_{h}$}
\ramec{170}{275}
\preghA{-160}
\stredA{235}{185}
\uzel{253}{$\eta\zeta$} \uzel{178}{$\rho$}
\podpisA{185}{235}{$z_{h_1}={\underline{z}}_{h} z_{h}$}
\end{tikzpicture}$$ Definitions in Lemma \[presna struktura\] yield ${\mbox{\rm pref}}_1(\mu_a)\neq {\mbox{\rm pref}}_1(\mu_b)$ and ${\mbox{\rm pref}}_1(\mu)\neq {\mbox{\rm pref}}_1(\eta)$, whence the equality set has in both cases rank at least two.

Case: ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ marked. {#both}
===========================================================================

From now on we shall suppose that both ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked. Consider Lemma \[presna struktura\]. It is easy to note that the case of the lemma has to take place, and moreover, the word $\tau$ is empty. Therefore $${{\rm eq}}(g,h)=\{\sigma \mu_a,\sigma \mu_b\},$$ with ${\mbox{\rm pref}}_1(\mu_a)=a$, ${\mbox{\rm pref}}_1(\mu_b)=b$, and ${\mbox{\rm suff}}_1(\mu_a)\neq {\mbox{\rm suff}}_1(\mu_b)$.

Note the following useful fact.

\[mirror\] Let $(g,h)$ be a counterexample such that ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked. Put $g_1={\overline{g}\hspace{2pt}}$ and $h_1={\overline{{h_{{\text{\tiny\bf m}}}}}\hspace{2pt}}$. Then the pair $(g_1,h_1)$ is again a counterexample such that ${\overline{g_1}\hspace{2pt}}$ and ${\overline{h_1}\hspace{2pt}}$ are marked, and $${{\rm eq}}(g_1,h_1)=\{{\overline{\sigma}\hspace{2pt}} {\overline{\mu_a}\hspace{2pt}},{\overline{\sigma}\hspace{2pt}}{\overline{\mu_b}\hspace{2pt}}\}.$$

The verification is straightforward.

In this section, we will also need to assume that the pair $(g,h)$ is a *shortest counterexample*. That is, $|\sigma\mu_a|+|\sigma\mu_b|$ is as small as possible. Shortest counterexample have the following important properties, which can be summarized as: there are no repeated overflows. The proof is similar to the proof of Lemma \[hyper technicke lema\]. If there is a repeated overflow, then we can decompose the counterexample into blocks, and find a shorter counterexample, namely the pair of successor morphisms. Since both ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked, we will consider their blocks, which are easier to deal with.

\[shortest1\] Let $(g,h)$ be a counterexample such that ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked. Let two nonempty prefixes $\sigma_1$ and $\sigma_2$ of $\sigma$ satisfy $g(\sigma_1)=h(\sigma_2)$. Then $(g,h)$ is not a shortest counterexample.

Lemma \[coref\] applied to morphisms ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ implies that pairs $({\overline{\sigma\mu_a}\hspace{2pt}},{\overline{\sigma\mu_a}\hspace{2pt}})$, $({\overline{\sigma\mu_b}\hspace{2pt}},{\overline{\sigma\mu_b}\hspace{2pt}})$ and $({\overline{\sigma_1}\hspace{2pt}},{\overline{\sigma_2}\hspace{2pt}})$ can be factorized into a sequence of pairs $({\overline{e}\hspace{2pt}},{\overline{f}\hspace{2pt}})$ and $({\overline{e'}\hspace{2pt}},{\overline{f'}\hspace{2pt}})$ such that ${\overline{g}\hspace{2pt}}({\overline{e}\hspace{2pt}})={\overline{h}\hspace{2pt}}({\overline{f}\hspace{2pt}})$ and ${\overline{g}\hspace{2pt}}({\overline{e'}\hspace{2pt}})={\overline{h}\hspace{2pt}}({\overline{f'}\hspace{2pt}})$. Turning to reversals and defining $g_1$ and $h_1$ as in we obtain words $w,w'\in {{\rm Eq}}(g_1,h_1)$ such that $$\begin{aligned}
g_1(w)&=h_1(w)=\sigma\mu_a, & g_1(w')&=h_1(w')=\sigma\mu_b.\end{aligned}$$ Note also that ${\overline{g_1}\hspace{2pt}}$ and ${\overline{h_1}\hspace{2pt}}$ are marked by Lemma \[seq1\].

Since $(\sigma_1,\sigma_2)$ is a prefix of both $(\sigma\mu_a,\sigma\mu_a)$ and $(\sigma\mu_b,\sigma\mu_b)$, the words $w$ and $w'$ have a nonempty common prefix. From $g\neq h$, it is also easy to see that $|w|+|w|'<|\sigma\mu_a|+|\sigma\mu_b|$. Lemma \[uprava\] concludes the proof.

\[shortest2\] Let $(g,h)$ be a shortest counterexample such that ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ marked. Let prefixes $\sigma_1$, $\sigma_2$, $\sigma_1'$ and $\sigma_2'$ of $\sigma$ satisfy $$\begin{aligned}
\label{16080}
    h(\sigma_2)^{-1}g(\sigma_1)=h(\sigma_2')^{-1}g(\sigma_1').\end{aligned}$$ Then $\sigma_1=\sigma_1'$ and $\sigma_2=\sigma_2'$.

Recall that we allow to be an equality of two "negative" words if $g(\sigma_1)<h(\sigma_2)$ and $g(\sigma_1')<h(\sigma_2')$.

Proceed by contradiction. Without loss of generality, we can suppose $|\sigma_1|>|\sigma_1'|$ and $|\sigma_2|>|\sigma_2'|$. Let $u_1$ be the longest common suffix of $\sigma_1$ and $\sigma_1'$, and let $u_2$ be the longest common suffix of $\sigma_2$ and $\sigma_2'$. We want to show that $$\begin{aligned}
\label{16081}
    g(\sigma_1u_1^{-1})=h(\sigma_2u_2^{-1}). \end{aligned}$$ From and $g(\sigma\mu_a)=h(\sigma\mu_a)$, we deduce $$\begin{aligned}
\label{16082}
g(\sigma_1'\sigma_1^{-1}\sigma\mu_a)&=h(\sigma_2'\sigma_2^{-1}\sigma\mu_a).\end{aligned}$$ If $u_1=\sigma_1'$ and $u_2=\sigma_2'$, then follows from . Otherwise, we apply Lemma \[cor1\] to morphisms ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ (note that the role of ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ is interchangeable since both are marked), and to pairs $$({\overline{\sigma_1'\sigma_1^{-1}\sigma\mu_a}\hspace{2pt}},{\overline{\sigma_2'\sigma_2^{-1}\sigma\mu_a}\hspace{2pt}})\quad \text{ and} \quad ({\overline{\sigma\mu_a}\hspace{2pt}},{\overline{\sigma\mu_a}\hspace{2pt}})$$ to obtain $$g(u_1\sigma_1^{-1}\sigma\mu_a)=h(u_2\sigma_2^{-1}\sigma\mu_a),$$ whence follows too.

The rest is Lemma \[shortest1\]. $$\begin{tikzpicture}
\dolseda{15}{40}{} \dolseda{110}{135}{}
 \draw (150pt,-\radek)--(-30pt,-\radek)--(-30pt,\radek)--(150pt,\radek);
 \draw[dashed] (150pt,\radek)--(210pt,\radek); \draw[dashed] (150pt,-\radek)--(210pt,-\radek);
 \stredA{40}{15} \stredA{135}{110} 
 \horuzel{5}{$g(\sigma_1')$} \doluzel{-5}{$h(\sigma_2')$}
 \horuzel{105}{$g(u_1)$} \doluzel{95}{$h(u_2)$} \draw[dashed] (80pt,\radek)--(80pt,-\radek);
 \horuhornad{-30}{135}{$g(\sigma_1)$} 
 \doludolpod{-30}{110}{$h(\sigma_2)$} 
\end{tikzpicture}$$

As a particular case, we point out the following corollary.

\[shortestcor\] Let $(g,h)$ be a shortest counterexample such that ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ marked. Let two prefixes $\sigma_1$ and $\sigma_2$ of $\sigma$ satisfy $g(\sigma_1)=h(\sigma_2)z_h$. Then $\sigma_1=\sigma_2=\sigma$.

The case: ${\mbox{\rm pref}}_1(\sigma)= a$ or ${\mbox{\rm suff}}_1(\sigma)= a$ {#sub1}
------------------------------------------------------------------------------

\[suba\]

In this subsection we show that the word $\sigma$ of a counterexample cannot start nor end by the letter $a$.

Since ${\vertg(a)\vert}>{\verth(a)\vert}$ and ${\mbox{\rm suff}}_1(\mu_c)=a$ for some $c\in A$, we have $$\begin{aligned}
\label{1022}
h(a)\in{\mbox{\rm suff}}(g(a)).\end{aligned}$$

\[spor pref a\] There is no counterexample such that both ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked and ${\mbox{\rm pref}}_1(\sigma)= a$ or ${\mbox{\rm suff}}_1(\sigma)= a$.

Let first ${\mbox{\rm pref}}_1(\sigma)= a$. As in the proof of Claim \[spor zg non-empty\], we obtain that $z_h$ and $h(a)$ have a common primitive root, say $t$. From we have that $t$ is a suffix of $g(a)$, which yields a contradiction with Claim \[nekomutuje s a\].

The case ${\mbox{\rm suff}}_1(\sigma)= a$ follows from the same considerations for morphisms ${\overline{g}\hspace{2pt}}$ and ${\overline{{h_{{\text{\tiny\bf m}}}}}\hspace{2pt}}$ by Lemma \[mirror\].

The case: ${\mbox{\rm pref}}_1(\sigma)={\mbox{\rm suff}}_1(\sigma)= b$ {#subkonec}
----------------------------------------------------------------------

\[subb\] In this subsection we shall suppose that $(g,h)$ is a counterexample such that ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are marked, and ${\mbox{\rm pref}}_1(\sigma)={\mbox{\rm suff}}_1(\sigma)=b$. We shall restrict possible counterexamples to the case $\mu_b\in b^+$.

We first fix some notation.

\[convention\]  

-   Denote by $\ell$ the maximal integer such that $b^{\ell}$ is a prefix of $\sigma$.

-   Denote by $k$ the maximal integer such that $b^{k}$ is a prefix of $\mu_b\sigma$.

-   Denote by $\ell'$ the maximal integer such that $b^{\ell'}$ is a suffix of $\sigma\mu_b$ or $\sigma\mu_a$ (the one of the two equality words ending with $b$).

-   Denote by $k'$ the maximal integer such that $b^{k'}$ is a suffix of $\sigma$.

We make use of Lemma \[mirror\] and suppose that $k'\geq \ell$. In other words, we shall work either with $(g,h)$ or with $({\overline{g}\hspace{2pt}}, {\overline{{h_{{\text{\tiny\bf m}}}}}\hspace{2pt}})$ depending on whether $\sigma$ has more $b$s in the front or in the rear.

We first present some auxiliary lemmas.

\[hb gb nekomutuji\] The words $g(b)$ and $h(b)$ do not commute.

Suppose, for a contradiction, that $t$ is the common primitive root of $g(b)$ and $h(b)$. Since ${\vertg(b)\vert}<{\verth(b)\vert}$, we deduce, by $g(\sigma)=h(\sigma)z_h$, that the first occurrence of $g(a)$ in $g(\sigma)$ is comparable with $t$, a contradiction with $g$ being marked.

${\verth(b)\vert}>(\ell+\ell'-1){\vertg(b)\vert}$.

The word $h(b)$ is comparable with $g(b)^{\ell}$ and suffix-comparable with $g(b)^{\ell'}$. If ${\verth(b)\vert}\leq(\ell+\ell'-1){\vertg(b)\vert}$, then $g(b)$ and $h(b)$ commute by Lemma \[factor\], a contradiction with Lemma \[hb gb nekomutuji\]. $$\begin{tikzpicture}
 \horA{0}{30}{$g(b)$} \horA{30}{60}{$g(b)$} \horA{60}{90}{$g(b)$} \horA{90}{120}{$g(b)$} 
 \hordashA{120}{170}{}
 \dolA{80}{110}{$g(b)$} \dolA{110}{140}{$g(b)$} \dolA{140}{170}{$g(b)$}
 \doldashA{0}{80}{}
 \doludolbra{0}{170}{$h(b)$}
\end{tikzpicture}$$

\[dlouhe zh\] ${\vertz_h\vert}>(\ell+k'-1){\vertg(b)\vert}$.

The word $z_h$ is comparable with $g(b)^{\ell}$, since $z_h$ is comparable with $h(b)$, and $g(b)^{\ell}$ is a prefix of $h(b)$. Also $z_h$ is suffix-comparable with $g(b)^{k'}$, by $g(\sigma)=h(\sigma)z_h$.

First suppose that ${\vertz_h\vert}\geq {\vertg(b)\vert}$. Now, if ${\vertz_h\vert}\leq (\ell+k'-1){\vertg(b)\vert}$, then $z_h$ and $g(b)$ commute by Lemma \[factor\], a contradiction with Claim \[nekomutuje s b\].

Suppose now that $z_h$ is shorter than $g(b)$. Recall that $g(b)$ is a prefix of $g(\mu_b)$, prefix of $h(b)$, and a suffix of $g(\sigma)$. From $g(\sigma)=h(\sigma)z_h$ and $z_hg(\mu_b)=h(\mu_b)$ we deduce that there is a word $v$ such that $g(b)=vz_h$ and at the same time $g(b)=z_hv$. Again, the words $g(b)$ and $z_h$ commute, a contradiction. $$\begin{tikzpicture}
\dolunulabra{20}{50}{{\small $z_h$}}
\horseda{20}{50}{}
\horuhorbra{0}{20}{{\small $v$}}
\horuhorbra{50}{70}{{\small $v$}}
\tecky{-30}{0} \draw (0,-\radek)--(20pt,-\radek);
\tecky{100}{160}
\horA{0}{50}{$g(b)$}  \horA{50}{100}{$g(b)$}
\dolA{20}{120}{$h(b)$}
\doludolbra{20}{70}{$g(b)$}
\end{tikzpicture}$$

An important step in the proof is the following lemma which shows that $g(a)$ cannot be too short.

\[existujeu\] $|g(ba)|>|h(b)|$.

In this proof we shall consider occurrences of $g(b)$s and $h(b)$s in $g(\sigma)$ and $h(\sigma)$, and their relative position. The idea is quite intuitive, but we give a more formal definition. Let $i,j\leq {\vert\sigma\vert}_b$ be positive integers. Denote by $u_i$ the prefix of $\sigma$ such that also $u_ib$ is a prefix of $\sigma$, and ${\vertu_ib\vert}_b=i$.

We say that the $i$th occurrence of $g(b)$ in $g(\sigma)$ <span>*starts*</span> within the $j$th occurrence of $h(b)$ in $h(\sigma)$, if $${\verth(u_j)\vert}\leq {\vertg(u_i)\vert}< {\verth(u_jb)\vert}.$$ Similarly, we say that the $i$th occurrence of $g(b)$ in $g(\sigma)$ <span>*ends*</span> within the $j$th occurrence of $h(b)$ in $h(\sigma)$, if $${\verth(u_j)\vert}< {\vertg(u_ib)\vert}\leq {\verth(u_jb)\vert}.$$

Lemma \[dlouhe zh\] immplies that the last occurrence of $g(b)$ in $g(\sigma)$ both starts and ends outside $h(\sigma)$. Therefore, by the pigeon hole principle, there is an occurrence of $h(b)$ in $h(\sigma)$ such that no occurrence of $g(b)$ in $g(\sigma)$ starts within it. Similarly, there is an occurrence of $h(b)$ in $h(\sigma)$ within which no $g(b)$ ends. From this it is easy to deduce that $h(b)$ is a prefix of $sg(a)^+$, and a suffix of $g(a)^+p$ where $s$ is a suffix of $g(b)$ or $g(a)$, and $p$ is a prefix of $g(b)$ or $g(a)$. Let $t$ be the primitive root of $g(a)$.

By $g(\sigma)=h(\sigma)z_h$, the words $h(b)$ and $g(b^\ell a)$ are prefix comparable. Suppose that $g(b^\ell t)$ is a prefix of $h(b)$. From the fact that $g(b^\ell)g(a)$ is a prefix of $sg(a)^+$ we deduce by Lemma \[factor\] that ${\overline{g}\hspace{2pt}}$ is not marked, a contradiction. Similarly, we obtain a contradiction with $g$ being marked, if $tg(b)^{\ell'}$ is a suffix of $h(b)$. Therefore $$\begin{aligned}
\label{dveb}
\text{  $|h(b)|<|g(b)^\ell t|$ and $|h(b)|<|t g(b)^{\ell'} |$}\end{aligned}$$ and we are through if $\ell=1$.

Suppose $\ell\geq 2$. Again by a pigeon hole principle, there are at least two occurrences of $h(b)$ in $g(\sigma)$ with no starting $g(b)$. Therefore $h(b)$ is a prefix of $s_1g(a)^+$ and $s_2g(a)^+$, where $s_1$ and $s_2$ are proper suffixes of $g(b)$ or $g(a)$. Note that $s_1$ and $s_2$ are overflows in $\sigma$, whence $s_1\neq s_2$ by Lemma \[shortest2\]. Suppose, for a contradiction, that $|g(ba)|\leq |h(b)|$. From $s_1\neq s_2$, it is then not difficult to deduce that $g(a)$ overlaps nontrivially with $g(a)^2$, whence it is not primitive and $|g(a)|\geq 2|t|$. From this and from we obtain $$2|h(b)|<|g(b)^\ell t|+|g(b)^{\ell'} t|\leq(\ell+\ell')|g(b)|+|g(a)|\leq(\ell+\ell'-1)|g(b)|+|h(b)|,$$ a contradiction with Lemma .

We can now once more point out two commuting words.

\[hb komutuje\] The word $h(b)$ commutes with $z_hg(b)^{k-\ell}$. $$\begin{tikzpicture}
\podpisA{0}{45}{{$z_h$}}
\horseda{0}{45}{}
\horuhornad{20}{45}{{\small $g(b)^{k'}$}}
\horuhornad{60}{90}{{\small $g(b)^{\ell}$}}
\horuhorbra{90}{185}{$u$}
\doludolbra{60}{185}{{\small $h(b)$}}
\tecky{-30}{0} \draw (0,\radek)--(60pt,\radek);
\tecky{220}{240} \draw (90pt,\radek)--(220pt,\radek);
\horA{45}{90}{$g(b)^k$}
\dolA{0}{110}{$h(b)$} \dolA{110}{220}{$h(b)$}
\node at (150pt,0.5*\radek){$g(a)$};
\end{tikzpicture}$$

Lemma \[dlouhe zh\] and the definition of $k'$ implies that $g(b)^{k'}$ is a suffix of $z_h$. The assumption $k'\geq \ell$ guarantees that $z_hg(b)^{k-\ell}$ is a well defined prefix of $z_hg(b)^k$.

Let $u$ be the word $g(b)^{-\ell}h(b)$, which is a prefix of $g(a)$ by Lemma \[existujeu\]. Since ${\verth(b)\vert}>{\vertg(b)\vert}$ and $\ell\geq 1$, we have $${\verth(b)^kz_h\vert}>{\vertz_hg(b)^{k-\ell}h(b)\vert}.$$ The equality $z_hg(\mu_b)=h(\mu_b)$ now implies that the word $$z_hg(b)^{k}u=z_hg(b)^{k-\ell}h(b)$$ is a prefix of $h(b)^+$ and thus $z_hg(b)^{k-\ell}$ commutes with $h(b)$ by Lemma \[factor\].

As a consequence, we have the claim of this section.

\[bb\] If $(g,h)$ is a shortest counterexample such that ${\mbox{\rm pref}}_1(\sigma)={\mbox{\rm suff}}_1(\sigma)=b$, then $\mu_b= b^{k-\ell}$.

Let $t$ be the common primitive root of words $h(b)$ and $z_hg(b)^{k-\ell}$. Recall that, by , the maximal $t$-prefix of any $h(au)z_h$ is $z_h$. We deduce the following.

-   The maximal $t$-prefix of $h(\sigma)z_h=g(\sigma)$ is $h(b)^\ell z_h$.

-   The maximal $t$-prefix of $h(\mu_b\sigma)z_h=z_h g(\mu_b\sigma)=z_h g(b)^{k-\ell}g(b^{\ell-k}\mu_b\sigma)$ is $h(b)^kz_h$, which implies that the maximal $t$-prefix of $g(b^{\ell-k}\mu_b\sigma)$ is $$(z_hg(b)^{k-\ell})^{-1}h(b)^kz_h=h(b)^kg(b)^{\ell-k}.$$

Since $\sigma$ contains $a$, both maximal $t$-prefixes mentioned above are proper.

Let first $h(b)^kg(b)^{\ell-k}\neq h(b)^\ell z_h$, and put $v=\sigma\wedge b^{\ell-k}\mu_b\sigma$.

If $|h(b)^kg(b)^{\ell-k}|> |h(b)^\ell z_h|$, then $g(v)=h(b)^\ell z_h$, by Lemma \[gprefix\], a contradiction with Lemma \[shortestcor\].

On the other hand, $|h(b)^kg(b)^{\ell-k}|< |h(b)^\ell z_h|$ implies $k<\ell$, and Lemma \[gprefix\] yields $g(v)=h(b)^kg(b)^{\ell-k}$ and $g(vb^{k-\ell})=h(b)^k$, a contradiction with Lemma \[shortest1\].

It remains that $h(b)^kg(b)^{\ell-k}= h(b)^\ell z_h$, which implies $h(b)^{k-\ell}=z_hg(b)^{k-\ell}$ and $\mu_b=b^{k-\ell}$.

The case: ${\mbox{\rm pref}}_1(\sigma)={\mbox{\rm suff}}_1(\sigma)= b$ and $\mu_b=b^{k-\ell}$ {#mub}
---------------------------------------------------------------------------------------------

This last case is most difficult because it in a way compresses two places we use for the analysis into one, namely the beginning of $\sigma$ and the beginning of $\mu_b$. $$\begin{tikzpicture}
\preghA{10}
\ramec{0}{250}
\stredA{80}{60} \stredA{190}{170}
\uzel{35}{$\sigma$} \uzel{95}{$b^{k-\ell}$} \uzel{125}{$b^{\ell}$} \uzel{150}{$( b^{-\ell}\sigma)$} \uzel{220}{$\mu_a$}
\draw[dashed](110pt,\radek)--(110pt,-\radek);
\end{tikzpicture}$$

Therefore, we have to employ a more detailed analysis of $\mu_a$.

There is no shortest counterexample with ${\mbox{\rm pref}}_1(\sigma)={\mbox{\rm suff}}_1(\sigma)=b$.

Claim \[bb\] implies ${\mbox{\rm pref}}_1(\mu_b)={\mbox{\rm suff}}_1(\mu_b)=b$ whence $${\mbox{\rm pref}}_1(\mu_a)={\mbox{\rm suff}}_1(\mu_a) = a.$$ Let $v_1$ be the longest prefix of $\mu_a$ ending with $a$ and satisfying $|z_hg(v_1)|>h(v_1)$. It follows that $\mu_a=v_1b^mv_2$ where $m>0$, ${\mbox{\rm suff}}_1(v_1)={\mbox{\rm pref}}_1(v_2)=a$ and $$\begin{aligned}
    |z_hg(v_1)|&>|h(v_1)|, &  |g(v_2)|&>|h(v_2)|.\end{aligned}$$ Denote $u_1=h(v_1)^{-1}z_hg(v_1)$ and $u_2=g(v_2)h(v_2)^{-1}$. $$\begin{tikzpicture}
\horuhorbra{50}{90}{$u_1$}
\horuhorbra{140}{200}{$u_2$}
\horA{90}{140}{$g(b)^m$}
\dolA{50}{200}{$h(b)^m$}
\tecky{0}{50} \tecky{200}{250}
\draw (50pt,\radek)--(200pt,\radek);
\horuzel{50}{$g(v_1)$} \horuzel{200}{$g(v_2)$}
\doluzel{25}{$h(v_1)$} \doluzel{225}{$h(v_2)$}
\end{tikzpicture}$$ From $|h(b)|>|g(b)|$ and $z_hg(b^{k-\ell})=h(b^{k-\ell})$ we obtain $$\begin{aligned}
\label{kratkehb}
    |h(b)|\leq|z_hg(b)|.\end{aligned}$$

Let now $y$ be the prefix of $g(ba)$ of length $h(b)$ and let $x$ be the word such that $xg(b)^{\ell'}=h(b)^{\ell'}$. From we deduce that $u_1g(b)^{m-1}y$ is a prefix of $h(b)^+$. Also $xg(b)^{\ell'+\ell-1}y$ is a prefix of $h(b)^+$. Lemma \[factor\] now implies that $u_1g(b)^{m-1}$ and $xg(b)^{\ell'+\ell-1}$ are suffix comparable. Since ${\overline{g}\hspace{2pt}}$ is marked and both $x$ and $u_1$ are suffix comparable with $g(a)$, we deduce $m=\ell+\ell'$.

From Lemma \[existujeu\], we obtain that $h(b)$ is a prefix of $g(b)^\ell g(a)$ whence the word $u_1g(b)^{\ell'}h(b)$ is a prefix of $h(b)^mz_h$. Lemma \[factor\] now implies that $u_1g(b)^{\ell'}$ commutes with $h(b)$.

Note that $u_1g(b)^{\ell'}$ is the maximal $h(b)$-suffix of $g(\sigma v_1b^{\ell'})$ and $xg(b)^{\ell'}$ is the maximal $h(b)$-suffix of $g(\sigma \mu_b)$. Minimality of $\sigma\mu_a$ implies that $$u_1g(b^{\ell'})\neq h(b^{\ell'})=xg(b^{\ell'}).$$ Let $v$ be the longest common suffix of $\sigma\mu_b$ and $\sigma v_1b^{\ell'}$. We apply Lemma \[gprefix\] to ${\overline{g}\hspace{2pt}}$ and obtain that $g(v)$, which is the longest common suffix of $g(\sigma\mu_b)$ and $g(\sigma v_1b^{\ell'})$, is equal either to $u_1g(b)^{\ell'}$ or to $xg(b)^{\ell'}$. In both cases, $g(v)$ commutes with $h(b)$; let $t$ be their common primitive root.

Since ${\overline{g}\hspace{2pt}}$ is marked, the maximal $t$-suffix of $g(\sigma\mu_b)$ is $g(u)$ where $u$ is the maximal $v$-suffix of $\sigma\mu_b$. Since ${\overline{h}\hspace{2pt}}$ is marked, the maximal $t$-suffix of $h(\sigma\mu_b)$ is $h(b^{\ell'})$. Therefore $g(\sigma\mu_b u^{-1} )=h(\sigma \mu_b b^{-\ell'})=h(\sigma b^{-k'})$, where $\sigma\mu_bu^{-1}$ is a prefix of $\sigma$ since $h(\sigma b^{-k'})$ is a prefix of $h(\sigma)$. Hence $(g,h)$ is not a shortest counterexample by Lemma \[shortest1\].

This concludes the proof that there is no counterexample. By Lemma \[uprava\], two minimal elements $\alpha$ and $\beta$ of ${{\rm Eq}}(g,h)$ cannot start with the same letter if $g$ and $h$ are both non-periodic. Clearly, also ${\overline{g}\hspace{2pt}}$ and ${\overline{h}\hspace{2pt}}$ are non-periodic and ${\overline{\alpha}\hspace{2pt}}$, ${\overline{\beta}\hspace{2pt}}$ are minimal elements of ${{\rm Eq}}({\overline{g}\hspace{2pt}},{\overline{h}\hspace{2pt}})$. Theorem \[hlavni veta\] is proved.

Test set {#test}
========

In this section we show that each binary language has a test set of cardinality at most two. The result is a consequence of Theorem \[char\] and Theorem \[hlavni veta\].

<span>*Test set*</span> of a language $L\subset \Sigma^*$ is defined as a subset $T$ of $L$ such that the agreement of two morphisms on the language $T$ guarantees their agreement on $L$. Formally, for any two morphisms $g$ and $h$ defined on $\Sigma^*$ $$(\forall\, u \in T)\ (\,g(u)=h(u)\,)\ \Rightarrow  (\forall\, v \in L)\ (\,g(v)=h(v)\,)\,.$$

The <span>*ratio*</span> of a word $u\in A^+$ is denoted by $r(u)$ and defined by $$r(u)=\frac{\ {\vertu\vert}_a}{\ {\vertu\vert}_b}\ .$$ If ${\vertu\vert}_b=0$, then $r(u)=\infty.$ A word $u$ is said to be <span>*ratio-primitive*</span> if no proper prefix of $u$ has the same ratio as $u$.

It is not difficult to see that each nonempty word $u$ has a unique factorization $u=u_1\dots u_k$ where each $u_i$ is a nonempty ratio-primitive word such that $r(u_i)=r(u)$. We call it the <span>*ratio-primitive factorization*</span> of $u$. Let ${{\rm R}}(L)$ denote the set of all ratio-primitive words $u$ such that $u$ occurs in the ratio-primitive factorization of at least one word in $L$.

\[ratio\] If ${\vertg(a)\vert}\neq {\verth(a)\vert}$, then ${\vertg(u)\vert}={\verth(u)\vert}$, $u\in A^+$, if and only if $$r(u)=\frac{{\verth(b)\vert}-{\vertg(b)\vert}}{{\vertg(a)\vert}-{\verth(a)\vert}}.$$ If ${\vertg(a)\vert}= {\verth(a)\vert}$ and ${\vertg(b)\vert}\neq {\verth(b)\vert}$, then ${\vertg(u)\vert}={\verth(u)\vert}$, $u\in A^+$, if and only if $r(u)=\infty$.

Follows directly from $${\vertg(u)\vert}=|u|_a\cdot{\vertg(a)\vert}+|u|_b\cdot {\vertg(b)\vert}\quad \text{and}\quad {\verth(u)\vert}=|u|_a\cdot{\verth(a)\vert}+|u|_b\cdot{\verth(b)\vert}.$$

An immediate corollary is the following fact.

\[staci rozklad\] Binary morphisms $g$ and $h$ agree on $L$ if and only if they agree on ${{\rm R}}(L)$.

Here is one more observation.

\[difratio\] If $g(u)=h(u)$ and $g(v)=h(v)$, with $u,v\in A^+$ and $r(u)\neq r(v)$, then $g=h$.

Since $r(u)\neq r(v)$, the word $uv$ contains both letters $a$ and $b$. Lemma \[ratio\] implies ${\vertg(a)\vert}= {\verth(a)\vert}$ and ${\vertg(b)\vert}={\verth(b)\vert}$ whence $g=h$.

We can now proof the main claim.

Let $L\subset A^*$ be a language. Then $L$ possesses a test set of cardinality at most two.

If $L$ contains words $u$ and $v$ with different ratios, then $T=\{u,v\}$ is a test set of $L$ by Lemma \[difratio\].

Suppose that all words in $L$ have the same ratio. We first find a test set $T_{{\rm R}}$ of cardinality at most two for ${{\rm R}}(L)$. If ${{\rm R}}(L)$ has cardinality at least three, let $T_{{\rm R}}=\{u,v\}$ where $u,v\in {{\rm R}}(L)$ and ${\mbox{\rm pref}}_1(u)= {\mbox{\rm pref}}_1(v)$.

Let $g$ and $h$ be morphisms such that $g\neq h$, $g(u)=h(u)$ and $g(v)=h(v)$. Since $u$ and $v$ are ratio-primitive, Lemma \[ratio\] implies that $u$ and $v$ are minimal elements of ${{\rm Eq}}(g,h)$. Therefore both morphisms are periodic by Theorem \[char\] and Theorem \[hlavni veta\]. By Theorem \[char\], we have ${{\rm R}}(L)\subseteq {{\rm Eq}}(g,h)$.

Let now $T$ be a subset of $L$ such that ${{\rm R}}(T)=T_{{\rm R}}$. Clearly, $T$ can be chosen such that its cardinality is at most two. Lemma \[staci rozklad\] concludes the proof.

{'source': 'arXiv_out/1209'}