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-order (wqo) less than or equal to and prove that a natural extension of this order 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 case one obtains a wqo. We prove that the above wqo's are effectively computable, that is, for any two regular languages (rational trees) one can decide whether they are comparable in the given wqo.
Intrigila, B., Varricchio, S. (2000). On the generalization of Higman and Kruskal's theorems to regular languages and rational trees. ACTA INFORMATICA, 36, 817-835 [10.1007/s002360050176].
On the generalization of Higman and Kruskal's theorems to regular languages and rational trees
INTRIGILA, BENEDETTO;VARRICCHIO, STEFANO
2000-01-01
Abstract
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-order (wqo) less than or equal to and prove that a natural extension of this order 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 case one obtains a wqo. We prove that the above wqo's are effectively computable, that is, for any two regular languages (rational trees) one can decide whether they are comparable in the given wqo.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
