2022/03/12 by Ondřej Klíma, Klíma, Ondřej, Jonatan Kolegar +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL
paper · pdf · doi:10.48550/arxiv.2203.06535
arxiv created 2022/03/12 · arxiv updated 2022/03/15
In 1985, Bucher, Ehrenfeucht and Haussler studied derivation relations associated with a given set of context-free rules. Their research motivated a question regarding homomorphisms from the semigroup of all words onto a finite ordered semigroup. The question is which of these homomorphisms induce a well quasi-order on the set of all words. We show that this problem is decidable and the answer does not depend on the homomorphism, but it is a property of the ordered semigroup.