Scattered one-counter languges have rank less than ω²

2020/06/30 by Ivan, Szabolcs
Computer Science · #Advanced Algebra and Logic #Coding theory and cryptography #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2007.00090

openalex publication_date 2020/06/30 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28

Abstract

A linear ordering is called context-free if it is the lexicographic ordering of some context-free language and is called scattered if it has no dense subordering. Each scattered ordering has an associated ordinal, called its rank. It is known that scattered context-free (regular, resp.) orderings have rank less than ω^ω (ω, resp). In this paper we confirm the conjecture that one-counter languages have rank less than ω².

Related

• The order type of scattered context-free orderings of rank one is computable
• Context-free ordinals
• The FC-rank of a context-free language
• Scattered context-free linear orderings
• On context-free languages of scattered words