Elementary Alphabets of a Language
The paper pertains to the field of Combinatorics on words. We introduce the notion of elementary alphabet of a language as the natural generalization of the combinatorial alphabet introduced in [10]. By analogy with the famous Ehrenfeucht conjecture, we prove a compactness property of all words in a language, namely, that any language has a finite elementary test-set. Then we show that the class of all elementary sets of a regular language can be effectively constructed. As a consequence, it is decidable whether a given finite part of a regular language is an elementary test-set for that language.
elementary alphabet combinatorics on words combinatorial alphabet elementary test-set combinatorial dimension