- ‘A language hierarchy of binary relations’
-
(with T. Brough)
Information and Computation 275 (December 2020).
Motivated by the study of word problems of monoids, we explore two ways of viewing binary relations on $X^*$ as languages. We exhibit a hierarchy of classes of binary relations on $X^*$, 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. Aside from the algebraic interest, these examples demonstrate that the hierarchy still holds when restricted to equivalence relations.