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 ${\omega }^2$, then its order type is effectively computable.

In Proceedings GandALF 2019, arXiv:1909.05979. arXiv admin note: text overlap with arXiv:1907.11573