On well quasiordering of finite languages (Q1356526)

A quasiordering on a set in which there exists neither an infinite antichain nor an infinite descending chain is called a well quasiordering. In the paper, finite languages (i.e. sets of strings) over an infinite countable set of symbols are considered. A quasiordering is introduced so that \(K\preceq L\) for two languages \(K,L\) if and only if it is possible to rename symbols occurring in the strings of \(L\) in such a way that any string of \(K\) is a subsequence of a string of the renamed \(L\). It is proved that \(\preceq\) is a well quasiordering, which is a solution of a problem posed by J. Gustedt. The same is proved for the quasiordering \(\preceq^*\), which is defined in the paper and which satisfies stronger conditions than \(\preceq\).