Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GA19-12790S" target="_blank" >GA19-12790S: Effective characterizations of classes of finite semigroups and formal languages</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theory of Computing Systems
ISSN
1432-4350
e-ISSN
1433-0490
Volume of the periodical
68
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
23
Pages from-to
380-402
UT code for WoS article
001200343100001
EID of the result in the Scopus database
2-s2.0-85190159569