On the Order Type of Scattered Context-Free Orderings

2019/09/17 by Kitti Gelle, Szabolcs Iván
Computer Science · #cs.FL

paper · pdf · doi:10.4204/eptcs.305.12

published as EPTCS 305, 2019, pp. 169-182 · In Proceedings GandALF 2019, arXiv:1909.05979. arXiv admin note: text overlap with arXiv:1907.11573

arxiv created 2019/09/17 · arxiv updated 2019/09/19

Abstract

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

Citations

• Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification
• The order type of scattered context-free orderings of rank one is computable