A language hierarchy of binary relations
Copyright policy )A language hierarchy of binary relations
Motivated by the study of word problems of monoids, we explore two ways of viewing binary relations on $A^*$ as languages. We exhibit a hierarchy of classes of binary relations on $A^*$, 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)
- University of Beira Interior Portugal
- Faculdade de Ciência e Tecnologia, Universidade Nova de Lisboa Portugal
- Universidade NOVA de Lisboa Portugal
- Universidade Nova de Lisboa Portugal
- Universidade Nova de Lisboa Portugal
context-free grammar, FOS: Computer and information sciences, Free semigroups, generators and relations, word problems, Formal Languages and Automata Theory (cs.FL), binary relations on words, Computer Science - Formal Languages and Automata Theory, 68Q45, 20M05, 20F10, 03D40, 08A50, Formal languages and automata, Group Theory (math.GR), indexed grammar, word problems, transducer, Semigroups in automata theory, linguistics, etc., Grammars and rewriting systems, FOS: Mathematics, linear indexed grammar, one-counter automaton, Mathematics - Group Theory, ET0L-system
context-free grammar, FOS: Computer and information sciences, Free semigroups, generators and relations, word problems, Formal Languages and Automata Theory (cs.FL), binary relations on words, Computer Science - Formal Languages and Automata Theory, 68Q45, 20M05, 20F10, 03D40, 08A50, Formal languages and automata, Group Theory (math.GR), indexed grammar, word problems, transducer, Semigroups in automata theory, linguistics, etc., Grammars and rewriting systems, FOS: Mathematics, linear indexed grammar, one-counter automaton, Mathematics - Group Theory, ET0L-system
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!