Growth and ergodicity of context-free languages II: The linear case

DOI10.1090/S0002-9947-06-03958-4zbMath1106.68059MaRDI QIDQ3420282

Tullio G. Ceccherini Silberstein

Publication date: 1 February 2007

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

growthergodicityambiguitycontext-free grammarautomatonlinear languagehigher block languagesbilateral automatondependency di-graph

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Asymptotic enumeration (05A16) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ On the growth of linear languages

Cites Work

• On the growth of linear languages
• Non-negative matrices and Markov chains. 2nd ed
• On the entropy of regular languages.
• Growth-sensitivity of context-free languages.
• Context-free languages of sub-exponential growth
• On a lemma of Gromov and the entropy of a graph
• On problems related to growth, entropy, and spectrum in group theory
• Growth and ergodicity of context-free languages
• An Introduction to Symbolic Dynamics and Coding
• A helpful result for proving inherent ambiguity
• On the entropy of context-free languages
• The growth function of context-free languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Growth and ergodicity of context-free languages II: The linear case