Context-free languages of sub-exponential growth

DOI10.1006/jcss.2001.1804zbMath1013.68123OpenAlexW1982097696MaRDI QIDQ1608320

Robert H. Gilman, Martin R. Bridson

Publication date: 4 August 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:d55e36d5-2cce-4de7-af0b-7fa20d8883ba

zbMATH Keywords

context-free languages

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items (15)

ON GROUPS WHOSE GEODESIC GROWTH IS POLYNOMIAL ⋮ 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 ⋮ 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 ⋮ Applications of L systems to group theory ⋮ FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME ⋮ The growth function of context-free languages ⋮ Growth and ergodicity of context-free languages II: The linear case ⋮ On the growth of linear languages ⋮ Growth and ergodicity of context-free languages

Uses Software

• ALGOL 60

Cites Work

• 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
• A note on decidability questions on presentations of word semigroups
• Bounded Algol-Like Languages
• The growth function of context-free languages

This page was built for publication: Context-free languages of sub-exponential growth