On the Order Type of Scattered Context-Free Orderings

Kitti Gelle
(University of Szeged, Hungary)
Szabolcs Iván
(University of Szeged, Hungary)

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.

In Jérôme Leroux and Jean-Francois Raskin: Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2019), Bordeaux, France, 2-3rd September 2019, Electronic Proceedings in Theoretical Computer Science 305, pp. 169–182.
Published: 18th September 2019.

ArXived at: https://dx.doi.org/10.4204/EPTCS.305.12 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org