The FC-rank of a context-free language

DOI10.1016/J.IPL.2013.01.005MaRDI QIDQ2377239zbMATH OpenOpenAlexFDO

Authors Arnaud Carayol, Zoltán Ésik

Publication date 28 June 2013

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

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)

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$.

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)