Growth-sensitivity of context-free languages.

DOI10.1016/S0304-3975(03)00095-1zbMath1059.68056OpenAlexW2053416900MaRDI QIDQ1426039

Wolfgang Woess, Tullio G. Ceccherini Silberstein

Publication date: 14 March 2004

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00095-1

zbMATH Keywords

GrowthAmbiguityErgodicityContext-free grammarDependency digraphHigher block languagesPerron--Frobenius eigenvalue

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Growth tight actions of product groups ⋮ Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ On the entropy of regular languages. ⋮ Context-free pairs of groups. II: Cuts, tree sets, and random walks ⋮ Growth of quasiconvex subgroups ⋮ Growth and ergodicity of context-free languages II: The linear case ⋮ On the growth of linear languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The theory of ends, pushdown automata, and second-order logic
• Non-negative matrices and Markov chains. 2nd ed
• Finite range random walk on free groups and homogeneous trees
• On the entropy of regular languages.
• Random walks on trees with finitely many cone types
• On problems related to growth, entropy, and spectrum in group theory
• Growth and ergodicity of context-free languages
• Groups of automorphisms of trees and their limit sets
• An Introduction to Symbolic Dynamics and Coding
• Random Walks on Infinite Graphs and Groups
• On the entropy of context-free languages