Binary Equality Languages

A binary equality language is the equality language of two binary homomorphisms, that is, the set

where g,h: {a,b};^* → Δ^*.

The binary equality languages constitute the simplest non-trivial class of equality languages.

We say that the homomorphism g: {a,b};^* → Δ^* is periodic if g(a) and g(b) commute. According to the periodicity of the homomorphisms g,h the structure of the binary equality languages is the following:

Both homomorphisms g,h are periodic

In this case Eq(g,h)={ε} or Eq(g,h)={ε}∪{α;|α|_a∕|α|_b=k} for some k≥0.

One of the homomorphisms g,h is periodic

In this case, up to the exchange of letters a and b, the equality language is the following: Eq(g,h)={aⁱba^j}^*, for some i,j≥0.

Both homomorphisms g,h are non-periodic

In this case Eq(g,h)={α , β}^* for some, possibly empty, words α and β.

If both words α and β are non-empty, then, up to the exchange of the letters a and b we obtain Eq(g,h)={aⁱb , baⁱ}^*.

If Eq(g,h) is generated by a single word, the exact structure of the equality language is still unknown. For more details see Binary equality sets with a single generator.

-- JanaHadravova - 18 Jun 2012