Context-free pairs of groups. II: Cuts, tree sets, and random walks

DOI10.1016/J.DISC.2011.07.026MaRDI QIDQ658032zbMATH OpenOpenAlexWikidataFDO

Authors Wolfgang Woess

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/0911.0134

zbMATH Keywords

random walkscontext-free languagesfree groupscuts in graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Discrete-time Markov processes on general state spaces (60J05) Random walks on graphs (05C81) General theory of random and stochastic dynamical systems (37H05)

Abstract: This is a continuation of the study, begun by Ceccherini-Silberstein and Woess, of context-free pairs of groups and the related context-free graphs in the sense of Muller and Schupp. Instead of the cones (connected components with respect to deletion of finite balls with respect to the graph metric), a more general approach to context-free graphs is proposed via tree sets consisting of cuts of the graph, and associated structure trees. The existence of tree sets with certain "good" properties is studied. With a tree set, a natural context-free grammar is associated. These investigations of the structure of context free pairs, resp. graphs are then applied to study random walk asymptotics via complex analysis.

Recommendations

• Context-free pairs of groups. I: Context-free pairs and graphs
• Context-free languages and random walks on groups
• Context-free groups and their structure trees.
• Context-Free Groups and Bass–Serre Theory
• Automorphism groups of context-free graphs

Cites work

• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3701842 (Why is no real title available?)
• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 2046058 (Why is no real title available?)
• scientific article; zbMATH DE number 1894276 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• Accessibility and Groups of Cohomological Dimension One
• Analytic combinatorics
• Context-free languages and random walks on groups
• Context-free pairs of groups. I: Context-free pairs and graphs
• Cutting up graphs
• Finite range random walk on free groups and homogeneous trees
• Finitely generated groups with the M. Hall property
• Full Banach Mean Values on Countable groups.
• Groups, the theory of ends, and context-free languages
• Growth and ergodicity of context-free languages
• Growth-sensitivity of context-free languages.
• Non-negative matrices and Markov chains.
• On the entropy of context-free languages
• Random Trees
• Random Walks on Infinite Graphs and Groups
• Random Walks on Infinite Graphs and Groups - a Survey on Selected topics
• Random walks and periodic continued fractions
• Return probabilities for random walk on a half-line
• Singularities of the Green function of a random walk on a discrete group
• Subgroups of Surface Groups are Almost Geometric
• The theory of ends, pushdown automata, and second-order logic
• Vertex-transitive graphs and accessibility

Cited in

(7)

• Self-avoiding walks and multiple context-free languages
• Groups, graphs, languages, automata, games and second-order monadic logic
• Formulae and asymptotics for coefficients of algebraic functions
• Context-free pairs of groups. I: Context-free pairs and graphs
• Context-free groups and their structure trees.
• Context-free languages and random walks on groups
• The language of self-avoiding walks

This page was built for publication: Context-free pairs of groups. II: Cuts, tree sets, and random walks

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