The FC-rank of a context-free language

DOI10.1016/J.IPL.2013.01.005zbMATH Open1272.68208arXiv1202.6275OpenAlexW1987809743MaRDI QIDQ2377239FDOQ2377239

Zoltán Ésik, Arnaud Carayol

Publication date: 28 June 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We prove that the finite condensation rank (FC-rank) of the lexicographic ordering of a context-free language is strictly less than $omeg{a}^{o}mega$.

Full work available at URL: https://arxiv.org/abs/1202.6275

zbMATH Keywords

formal languagescontext-free languagelinear orderingcondensation rank

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Cited In (2)

• The ordinal generated by an ordinal grammar is computable
• Isomorphisms of scattered automatic linear orders

This page was built for publication: The FC-rank of a context-free language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2377239)