A Language Hierarchy of Binary Relations

Abstract

Motivated by the study of word problems of monoids, we explore two ways of viewing binary relations on $A^{\ast }$ as languages. We exhibit a hierarchy of classes of binary relations on $A^{\ast }$, according to the class of languages the relation belongs to and the chosen viewpoint. We give examples of word problems of monoids distinguishing the various classes.

19 pages, 2 figures (Several new examples added)