The FC-rank of a context-free language

2012/02/28 by Arnaud Carayol, Carayol, Arnaud, Zoltán Ésik +1 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #Advanced Algebra and Logic #DNA and Biological Computing

paper · pdf · doi:10.48550/arxiv.1202.6275

Abstract

We prove that the finite condensation rank (FC-rank) of the lexicographic ordering of a context-free language is strictly less than ω^ω.

Cited by

• Isomorphisms of scattered automatic linear orders

Related

• Scattered one-counter languges have rank less than ω²
• Context-free ordinals
• The order type of scattered context-free orderings of rank one is computable
• An undecidable property of context-free languages
• Scattered context-free linear orderings