On the growth of linear languages

DOI10.1016/J.AAM.2005.01.002MaRDI QIDQ817237zbMATH OpenOpenAlexFDO

Authors Tullio 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

context-free grammargrowth functionoriented graphlinear languagepolynomial and exponential growth

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Finding the growth rate of a regular or context-free language in polynomial time
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Growth and ergodicity of context-free languages II: The linear case
• Growth-sensitivity of context-free languages.
• Growth and ergodicity of context-free languages

Cites work

• scientific article; zbMATH DE number 3808970 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 812874 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A growth criterion for graphs and algebras defined by words
• A helpful result for proving inherent ambiguity
• An example of an indexed language of intermediate growth
• Bounded Algol-Like 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
• Growth-sensitivity of context-free languages.
• On the entropy of context-free languages
• On the entropy of regular languages.
• The growth function of context-free languages

Cited in

(9)

• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• Non-closure under complementation for unambiguous linear grammars
• Deciding regularity of hairpin completions of regular languages in polynomial time
• Growth-sensitivity of context-free languages.
• Groups, graphs, languages, automata, games and second-order monadic logic
• Finding the growth rate of a regular or context-free language in polynomial time
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Volume formula and growth rates of the balls of strings under the edit distances
• Growth and ergodicity of context-free languages II: The linear case

Describes a project that uses

Uses Software

• ALGOL 60

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

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