← 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 ∀u∈U,∃r∈R,r<u<rω\forall u \in U, \exists r \in R, r < u < r^\omega ∃u∈U,r∈R,r<u<rω∧∣r−1u∣>∣∣U∣∣\exists u \in U, r \in R, r < u < r^\omega \wedge |r^{-1}u| > ||U|| where ∣∣U∣∣||U|| is the number of states of the minimal automaton recognizing UU, and rωr^\omega is the infinite iteration of rr. 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.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu