A language hierarchy of binary relations

Tara Brough; Alan J. Cain

doi:10.1016/j.ic.2020.104607

A language hierarchy of binary relations

Tara Brough, Alan J. Cain

CMA - Centro de Matemática e Aplicações

Research output: Contribution to journal › Article › peer-review

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 language	English
Article number	104607
Journal	Information and Computation
Volume	275
DOIs	https://doi.org/10.1016/j.ic.2020.104607
Publication status	Published - Dec 2020

Keywords

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

Access to Document

10.1016/j.ic.2020.104607

Cite this

@article{c99ce66a8554475abab8afe69594c3ee,

title = "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 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.",

keywords = "Binary relations on words, Context-free grammar, ET0L-system, Indexed grammar, Linear indexed grammar, One-counter automaton, Transducer, Word problems",

author = "Tara Brough and Cain, {Alan J.}",

note = "SFRH/BPD/121469/2016 IF/01622/2013/CP1161/CT0001 UIDB/00297/2020 PTDC/MAT-PUR/31174/2017 PTDC/MAT-PUR/31174/2017",

year = "2020",

month = dec,

doi = "10.1016/j.ic.2020.104607",

language = "English",

volume = "275",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "ACADEMIC PRESS INC ELSEVIER SCIENCE",

}

TY - JOUR

T1 - A language hierarchy of binary relations

AU - Brough, Tara

AU - Cain, Alan J.

N1 - SFRH/BPD/121469/2016 IF/01622/2013/CP1161/CT0001 UIDB/00297/2020 PTDC/MAT-PUR/31174/2017 PTDC/MAT-PUR/31174/2017

PY - 2020/12

Y1 - 2020/12

N2 - 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.

AB - 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.

KW - Binary relations on words

KW - Context-free grammar

KW - ET0L-system

KW - Indexed grammar

KW - Linear indexed grammar

KW - One-counter automaton

KW - Transducer

KW - Word problems

UR - http://www.scopus.com/inward/record.url?scp=85089152120&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104607

DO - 10.1016/j.ic.2020.104607

M3 - Article

AN - SCOPUS:85089152120

SN - 0890-5401

VL - 275

JO - Information and Computation

JF - Information and Computation

M1 - 104607

ER -

A language hierarchy of binary relations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this