Well Quasi-Orders Arising from Finite Ordered Semigroups

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.

Date and Venue

Start Date
Online Zoom meeting
End Date


Ondřej Klíma

Speaker's Institution

Masaryk University, Czech Republic



Semigroups, Automata and Languages