← All problems
Unverified
Regular antichain subset of the iteration of a regular language
This problem comes from a typing problem (non structural subtype assignment). Given a regular language R, does there exist a regular language U such that: U is an antichain for the prefix ordering where is the number of states of the minimal automaton recognizing , and is the infinite iteration of . I conjecture that such language does not exist, though I don't find an approach to attack it. If such a language does exist, it would be interesting to know if there can be an infinite number of words such that the third point holds or not.
