There's a slight problem in this definition: to be non-trivial, it should be stated that only a proper subset of all equivalence relations are given and the goal is either:

  • to determine whether two particular elements are in the same equivalence class; or
  • to define completely all equivalence classes.

This is equivalent to the finding the connected components of an undirected graph. (The elements are vertices and equivalence is represented by edges.) The connected component problem is probably much better known; a brief web search revealed several class notes but only one published reference to the dynamic equivalence problem: Data Structures and Algorithm Analysis, by Mark Allen Weiss (Addison Wesley, 1997).