Other formats:
BibTeX
LaTeX
RIS
@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 and Jonatan KOLEGAR. Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words. \textit{Theory of Computing Systems}. New York: Springer, 2024, vol.~68, No~3, p.~380-402. ISSN~1432-4350. Available from: https://dx.doi.org/10.1007/s00224-024-10172-0.
|