Characterization of Ordered Semigroups Generating Well
Quasi-Orders of Words

J 2024

Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words

KLÍMA, Ondřej a Jonatan KOLEGAR

Základní údaje

Originální název

Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words

Autoři

KLÍMA, Ondřej (203 Česká republika, domácí) a Jonatan KOLEGAR (203 Česká republika, domácí)

Vydání

Theory of Computing Systems, New York, Springer, 2024, 1432-4350

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.500 v roce 2022

Organizační jednotka

Přírodovědecká fakulta

DOI

http://dx.doi.org/10.1007/s00224-024-10172-0

UT WoS

001200343100001

Klíčová slova anglicky

Finite semigroups; Well quasi-orders; Unavoidable words; Derivation relations; Ordered semigroups

Štítky

rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 29. 7. 2024 08:37, Mgr. Marie Šípková, DiS.

Anotace

V originále

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ávaznosti

GA19-12790S, projekt VaV

Název: Efektivní charakterizace tříd konečných pologrup a formálních jazyků

Investor: Grantová agentura ČR, Efektivní charakterizace tříd konečných pologrup a formálních jazyků

Citovat

KLÍMA, Ondřej a Jonatan KOLEGAR. Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words. Theory of Computing Systems. New York: Springer, 2024, roč. 68, č. 3, s. 380-402. ISSN 1432-4350. Dostupné z: https://dx.doi.org/10.1007/s00224-024-10172-0.

@article{2420579,
   author = {Klíma, Ondřej and Kolegar, Jonatan},
   article_location = {New York},
   article_number = {3},
   doi = {http://dx.doi.org/10.1007/s00224-024-10172-0},
   keywords = {Finite semigroups; Well quasi-orders; Unavoidable words; Derivation relations; Ordered semigroups},
   language = {eng},
   issn = {1432-4350},
   journal = {Theory of Computing Systems},
   title = {Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words},
   url = {https://link.springer.com/article/10.1007/s00224-024-10172-0},
   volume = {68},
   year = {2024}
}

TY  - JOUR
ID  - 2420579
AU  - Klíma, Ondřej - Kolegar, Jonatan
PY  - 2024
TI  - Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words
JF  - Theory of Computing Systems
VL  - 68
IS  - 3
SP  - 380-402
EP  - 380-402
PB  - Springer
SN  - 14324350
KW  - Finite semigroups
KW  - Well quasi-orders
KW  - Unavoidable words
KW  - Derivation relations
KW  - Ordered semigroups
UR  - https://link.springer.com/article/10.1007/s00224-024-10172-0
N2  - 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.
ER  -

KLÍMA, Ondřej a Jonatan KOLEGAR. Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words. \textit{Theory of Computing Systems}. New York: Springer, 2024, roč.~68, č.~3, s.~380-402. ISSN~1432-4350. Dostupné z: https://dx.doi.org/10.1007/s00224-024-10172-0.

Podrobný výpis o publikaci