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
Venue
Online Zoom meeting
End Date

Speaker

Ondřej Klíma

Speaker's Institution

Masaryk University, Czech Republic

Files

Area

Semigroups, Automata and Languages

Financiamento