On the generalization of Higman and Kruskal's theorems to regular languages and rational trees

In this paper we give new extensions and generalizations of the Higman and Kruskal theorems. We start with an alphabet A equipped by a well quasi-orde r (wqo) less than or equal to and prove that a natural extension of this or der to the family of regular languages over A is a wqo. A similar extension is given for rational trees with labels in A, proving that also in this ca se one obtains a wqo. We prove that the above wqo's are effectively computa ble, that is, for any two regular languages (rational trees) one can decide whether they are comparable in the given wqo.