A language hierarchy of binary relations

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number104607
JournalInformation and Computation
Publication statusPublished - Dec 2020


  • Binary relations on words
  • Context-free grammar
  • ET0L-system
  • Indexed grammar
  • Linear indexed grammar
  • One-counter automaton
  • Transducer
  • Word problems


Dive into the research topics of 'A language hierarchy of binary relations'. Together they form a unique fingerprint.

Cite this