Equality Languages

The equality language of the homomorphisms g,h: Σ^* → Δ^* is the set of all words from Σ^* on which the homomorphisms g and h agree. It is denoted by Eq(g,h) and more precisely defined as:

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

The simplest non-trivial class of equality languages is the binary equality languages, that is, the equality languages of binary homomorphisms. Even though binary equality languages are the simplest non-trivial equality languages, their precise structure is still unknown.

Open problems related to equality languages:

• Is PCP(3) Decidable?

References:

-- JanaHadravova - 22 May 2012