2012 | OriginalPaper | Chapter
Hausdorff Rank of Scattered Context-Free Linear Orders
Authors : Zoltán Ésik, Szabolcs Iván
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
ω
ω
. As an application of this result, we obtain that an ordinal is the order type of the lexicographic ordering of a context-free language if and only if it is less than
$\omega^{\omega^\omega}$
.