[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |

*Originator: H.-C. Kong *

*Date: December 1991*

Summary: Is embedding a well-quasi-ordering on strings?

Consider the following relation on strings over an infinite set
*X* of variables:
*x*_{1} *x*_{2} ⋯ *x*_{m} ↪ *y*_{1} *y*_{2} ⋯ *y*_{n} if there exists a
renaming ρ : *X* → *X* such that
*x*_{i} ρ = *y*_{ji} for 1 ≤ *j*_{1} < *j*_{2} < ⋯ < *j*_{m} ≤ *n*.
Is this “embedding” relation ↪ a well-quasi-ordering (that
is, must every infinite sequence of strings contain two strings, such that the
first embeds in the second)?

The answer is “yes”. (Map each variable to the position of its leftmost occurrence and use the fact that strings of natural numbers are well-quasi-ordered by the embedding extension of ≤ to strings.)

[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |