Widths of regular and context-free languages

David Mestel

Given a partially-ordered finite alphabet $\Sigma$ and a language $L\subseteq {\Sigma }^{\ast }$, how large can an antichain in $L$ be (where $L$ is given the lexicographic ordering)? More precisely,…