On prouve que tout langage commutatif sur un alphabet à n lettre possède un ensemble test de taille O ( n~2 ). Si l'image de Parikh du langage est un ensemble linéaire, la taille minimale de l'ensemble test est O(n log n). On prouve l'existence d'un langage commutatif fini sur un alphabet à n lettres pour lequel la taille du plus petit ensemble test est Ω (n~2 ).%It is proved that any commutative language over an alphabet of n symbols possesses a test set of size O (n~2). If the Parikh-map of the language is a linear set, then the minimum size of the test set is O (n log n). A finite commutative language over an alphabet of n symbols such that the smallest test set for the language is of size Ω (n~2) is shown to exist.
展开▼
