Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F24%3A00139487" target="_blank" >RIV/00216224:14310/24:00139487 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/article/10.1007/s00224-024-10172-0" target="_blank" >https://link.springer.com/article/10.1007/s00224-024-10172-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00224-024-10172-0" target="_blank" >10.1007/s00224-024-10172-0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words

Popis výsledku v původním jazyce

The notion of a quasi-order generated by a homomorphism from the semigroup of all words onto a finite ordered semigroup was introduced by Bucher et al. (Theor. Comput. Sci. 40, 131-148 1985). It naturally occurred in their studies of derivation relations associated with a given set of context-free rules, and they asked a crucial question, whether the resulting relation is a well quasi-order. We answer this question in the case of the quasi-order generated by a semigroup homomorphism. We show that the answer does not depend on the homomorphism, but it is a property of its image. Moreover, we give an algebraic characterization of those finite semigroups for which we get well quasi-orders. This characterization completes the structural characterization given by Kunc (Theor. Comput. Sci. 348, 277-293 2005) in the case of semigroups ordered by equality. Compared with Kunc's characterization, the new one has no structural meaning, and we explain why that is so. In addition, we prove that the new condition is testable in polynomial time.

Název v anglickém jazyce

Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words

Popis výsledku anglicky

The notion of a quasi-order generated by a homomorphism from the semigroup of all words onto a finite ordered semigroup was introduced by Bucher et al. (Theor. Comput. Sci. 40, 131-148 1985). It naturally occurred in their studies of derivation relations associated with a given set of context-free rules, and they asked a crucial question, whether the resulting relation is a well quasi-order. We answer this question in the case of the quasi-order generated by a semigroup homomorphism. We show that the answer does not depend on the homomorphism, but it is a property of its image. Moreover, we give an algebraic characterization of those finite semigroups for which we get well quasi-orders. This characterization completes the structural characterization given by Kunc (Theor. Comput. Sci. 348, 277-293 2005) in the case of semigroups ordered by equality. Compared with Kunc's characterization, the new one has no structural meaning, and we explain why that is so. In addition, we prove that the new condition is testable in polynomial time.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA19-12790S" target="_blank" >GA19-12790S: Efektivní charakterizace tříd konečných pologrup a formálních jazyků</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theory of Computing Systems

ISSN

1432-4350

e-ISSN

1433-0490

Svazek periodika

68

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

380-402

Kód UT WoS článku

001200343100001

EID výsledku v databázi Scopus

2-s2.0-85190159569