Informace o publikaci

Well Quasi-Orders Arising from Finite Ordered Semigroups

Logo poskytovatele
Autoři

KLÍMA Ondřej KOLEGAR Jonatan

Rok publikování 2022
Druh Článek ve sborníku
Konference Developments in Language Theory: 26th International Conference, DLT 2022
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www https://link.springer.com/chapter/10.1007/978-3-031-05578-2_16
Doi http://dx.doi.org/10.1007/978-3-031-05578-2_16
Klíčová slova Finite semigroups; Well quasi-orders; Unavoidable words
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info