The growth function of context-free languages

DOI10.1016/S0304-3975(00)00152-3MaRDI QIDQ5941088zbMATH OpenFDO

Authors Roberto Incitti

Publication date 20 August 2001

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

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00152-3

zbMATH Keywords

context-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• An example of an indexed language of intermediate growth
• Analytic models and ambiguity of context-free languages
• Bounded Algol-Like Languages
• Context-free languages of sub-exponential growth
• Formal language theory and the geometry of 3-manifolds
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)

Cited in

(23)

• The Parikh counting functions of sparse context-free languages are quasi-polynomials
• Growth rates of power-free languages
• On universally easy classes for NP-complete problems.
• Context-free languages of sub-exponential growth
• On bounded linear codes and the commutative equivalence
• On the structure of the counting function of sparse context-free languages.
• On the density of regular and context-free languages
• Growth and ergodicity of context-free languages
• Growth and ergodicity of context-free languages II: The linear case
• scientific article; zbMATH DE number 6503311 (Why is no real title available?)
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Groups, graphs, languages, automata, games and second-order monadic logic
• The monoids of the patience sorting algorithm
• On differentiation functions, structure functions, and related languages of context-free grammars
• The binomial equivalence classes of finite words
• 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
• Quasi-isometric reductions between infinite strings
• On the intersection problem for quantum finite automata
• Weighing obese timed languages
• On the growth of linear languages
• On block pumpable languages

Describes a project that uses

Uses Software

• ALGOL 60

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

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