Growth and ergodicity of context-free languages

DOI10.1090/S0002-9947-02-03048-9zbMath1016.68047OpenAlexW1769684122MaRDI QIDQ3151247

Wolfgang Woess, Tullio G. Ceccherini Silberstein

Publication date: 7 October 2002

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

Full work available at URL: https://doi.org/10.1090/s0002-9947-02-03048-9

zbMATH Keywords

growthergodicityambiguitycontext-free grammarPerron-Frobenius eigenvaluehigher block languages

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Geometric group theory (20F65) Asymptotic enumeration (05A16)

Related Items

Average-case complexity of the Whitehead problem for free groups, Self-avoiding walks and multiple context-free languages, Growth tight actions of product groups, The Poisson boundary of lamplighter random walks on trees, The language of self-avoiding walks, 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, Context-free pairs of groups. I: Context-free pairs and graphs, On the entropy of regular languages., Growth-sensitivity of context-free 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Growth series and random walks on some hyperbolic graphs.
• Groups, the theory of ends, and context-free languages
• The theory of ends, pushdown automata, and second-order logic
• Context-free languages and random walks on groups
• Non-negative matrices and Markov chains. 2nd ed
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• An example of an indexed language of intermediate growth
• Finite range random walk on free groups and homogeneous trees
• On the entropy of regular languages.
• Context-free languages of sub-exponential growth
• Random walks on trees with finitely many cone types
• Growth tightness for word hyperbolic groups.
• On problems related to growth, entropy, and spectrum in group theory
• A note on curvature and fundamental group
• Growth of finitely generated solvable groups
• Growth of finitely generated solvable groups and curvature of Riemannian manifolds
• Growth Series of Some Wreath Products
• 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
• The growth function of context-free languages