On the growth of linear languages

DOI10.1016/j.aam.2005.01.002zbMath1084.68060OpenAlexW2062203804MaRDI QIDQ817237

Tullio G. Ceccherini Silberstein

Publication date: 8 March 2006

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aam.2005.01.002

zbMATH Keywords

oriented graphgrowth functioncontext-free grammarlinear languagepolynomial and exponential growth

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Non-closure under complementation for unambiguous linear grammars ⋮ Volume formula and growth rates of the balls of strings under the edit distances ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Deciding regularity of hairpin completions of regular languages in polynomial time ⋮ Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract) ⋮ Growth and ergodicity of context-free languages II: The linear case

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A growth criterion for graphs and algebras defined by words
• An example of an indexed language of intermediate growth
• On the entropy of regular languages.
• Growth-sensitivity of context-free languages.
• Context-free languages of sub-exponential growth
• Growth and ergodicity of context-free languages
• Growth and ergodicity of context-free languages II: The linear case
• Bounded Algol-Like Languages
• A helpful result for proving inherent ambiguity
• On the entropy of context-free languages
• The growth function of context-free languages

This page was built for publication: On the growth of linear languages