A language hierarchy of binary relations

Research output: Contribution to journalArticle

Abstract

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
Volume275
DOIs
Publication statusPublished - Dec 2020

Keywords

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

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

Cite this