On the Order Type of Scattered Context-Free Orderings

Abstract

We show that if a context-free grammar generates a language whose lexicographic ordering is well-ordered of type less than ω^2, then its order type is effectively computable.