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

In this case *Eq(g,h)={ε}* or *Eq(g,h)={ε}∪{α;|α| _{a}∕|α|_{b}=k}* for some

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

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

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

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

Copyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback