[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #48 (Solved !)

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₁ x₂ ⋯ x_m ↪ y₁ y₂ ⋯ y_n if there exists a renaming ρ : X → X such that x_i ρ = y_ji for 1 ≤ j₁ < j₂ < ⋯ < 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)?

Remark

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]