Nerode equivalence
Let be a semigroup and let . The relation
(1) |
is an equivalence relation over , called the Nerode equivalence of .
As an example, if and then iff .
The Nerode equivalence is right-invariant, i.e., if then for any . However, it is usually not a congruence.
The Nerode equivalence is maximal in the following sense:
-
•
if is a right-invariant equivalence over and is union of classes of ,
-
•
then implies .
In fact, let : since and is right-invariant, . However, is union of classes of , therefore and are either both in or both outside . This is true for all , thus .
The Nerode equivalence is linked to the syntactic congruence by the following fact, whose proof is straightforward:
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 |