Nerode equivalence


Let S be a semigroupPlanetmathPlanetmath and let XS. The relationMathworldPlanetmathPlanetmath

s1𝒩Xs2tS(s1tXs2tX) (1)

is an equivalence relationMathworldPlanetmath over S, called the Nerode equivalence of X.

As an example, if S=(,+) and X={nkn=3k}, then m𝒩Xn iff mmod3=nmod3.

The Nerode equivalence is right-invariant, i.e., if s1𝒩Xs2 then s1t𝒩Xs2t for any t. However, it is usually not a congruencePlanetmathPlanetmathPlanetmathPlanetmath.

The Nerode equivalence is maximal in the following sense:

  • if η is a right-invariant equivalence over S and X is union of classes of η,

  • then sηt implies s𝒩Xt.

In fact, let rS: since sηt and η is right-invariant, srηtr. However, X is union of classes of η, therefore sr and tr are either both in X or both outside X. This is true for all rS, thus s𝒩Xt.

The Nerode equivalence is linked to the syntactic congruence by the following fact, whose proof is straightforward:

s1Xs2iffls1𝒩Xls2lS.
Title Nerode equivalence
Canonical name NerodeEquivalence
Date of creation 2013-03-22 18:52:11
Last modified on 2013-03-22 18:52:11
Owner Ziosilvio (18733)
Last modified by Ziosilvio (18733)
Numerical id 4
Author Ziosilvio (18733)
Entry type Definition
Classification msc 68Q70
Classification msc 20M35
Defines maximality property of Nerode equivalence