pith. sign in

arxiv: 1103.5421 · v1 · pith:YTRRSGEFnew · submitted 2011-03-28 · 💻 cs.FL

Context-free ordinals

classification 💻 cs.FL
keywords omegacontext-freelanguagelesslexicographicorderingconsidercorollary
0
0 comments X
read the original 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}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.