Binary Equality Languages

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

Eq(g,h)={w : g(w)=h(w)},

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)={aibaj}*, 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)={aib , bai}*.

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

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2012-06-22 - JeffreyShallit
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback