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

DOI10.1016/J.DISC.2011.07.026zbMATH Open1248.37044arXiv0911.0134OpenAlexW1968015827WikidataQ40386735 ScholiaQ40386735MaRDI QIDQ658032FDOQ658032

Authors: Wolfgang Woess 

Publication date: 11 January 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (6)

• Self-avoiding walks and multiple context-free languages
• Context-free pairs of groups. I: Context-free pairs and graphs
• Groups, graphs, languages, automata, games and second-order monadic logic
• Formulae and Asymptotics for Coefficients of Algebraic Functions
• The language of self-avoiding walks
• Context-free languages and random walks on groups

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)