The growth function of context-free languages

DOI10.1016/S0304-3975(00)00152-3zbMath0973.68117MaRDI QIDQ5941088

Roberto Incitti

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

context-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

On differentiation functions, structure functions, and related languages of context-free grammars ⋮ Ideals of equations for elements in a free group and context-free languages ⋮ Volume formula and growth rates of the balls of strings under the edit distances ⋮ On the Commutative Equivalence of Algebraic Formal Series and Languages ⋮ On block pumpable languages ⋮ On universally easy classes for NP-complete problems. ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time ⋮ On bounded linear codes and the commutative equivalence ⋮ The monoids of the patience sorting algorithm ⋮ On the structure of the counting function of sparse context-free languages. ⋮ ON THE DENSITY OF REGULAR AND CONTEXT-FREE LANGUAGES ⋮ The binomial equivalence classes of finite words ⋮ The Parikh counting functions of sparse context-free languages are quasi-polynomials ⋮ Growth and ergodicity of context-free languages II: The linear case ⋮ Context-free languages of sub-exponential growth ⋮ On the growth of linear languages ⋮ Growth and ergodicity of context-free languages

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Analytic models and ambiguity of context-free languages
• An example of an indexed language of intermediate growth
• Formal language theory and the geometry of 3-manifolds
• Context-free languages of sub-exponential growth
• Bounded Algol-Like Languages

This page was built for publication: The growth function of context-free languages