Context-free ordinals

Abstract

We consider context-free languages equipped with the lexicographic ordering. We show that when the lexicographic ordering of a context-free language is scattered, then its Hausdorff rank is less than ${\omega }^{\omega }$. As a corollary of this result we obtain that an ordinal is the order type of a well-ordered context-free language iff it is less than ${\omega }^{{\omega }^{\omega }}$.

References in corpus (1)

• Scattered context-free linear orderings

Cited by in corpus (1)

• On context-free languages of scattered words