  Given a partially-ordered finite alphabet $\Sigma$ and a language $L\subseteq
\Sigma^*$, how large can an antichain in $L$ be (where $L$ is given the
lexicographic ordering)? More precisely, since $L$ will in general be infinite,
we should ask about the rate of growth of maximum antichains consisting of
words of length $n$. This fundamental property of partial orders is known as
the width, and in a companion work we show that the problem of computing the
information leakage permitted by a deterministic interactive system modeled as
a finite-state transducer can be reduced to the problem of computing the width
of a certain regular language. In this paper, we show that if $L$ is regular
then there is a dichotomy between polynomial and exponential antichain growth.
We give a polynomial-time algorithm to distinguish the two cases, and to
compute the order of polynomial growth, with the language specified as an NFA.
For context-free languages we show that there is a similar dichotomy, but now
the problem of distinguishing the two cases is undecidable. Finally, we
generalise the lexicographic order to tree languages, and show that for regular
tree languages there is a trichotomy between polynomial, exponential and doubly
exponential antichain growth.
