Scattered context-free linear orderings

Zoltan Ésik

Abstract. We show that it is decidable in exponential time whether the lexicographic ordering of a context-free language is scattered, or a well-ordering.

Comments are closed.