Context-free groups and their structure trees.
From MaRDI portal
Abstract: Let Gamma be a connected, locally finite graph of finite tree width and G be a group acting on it with finitely many orbits and finite node stabilizers. We provide an elementary and direct construction of a tree T on which G acts with finitely many orbits and finite vertex stabilizers. Moreover, the tree is defined directly in terms of the structure tree of optimally nested cuts of Gamma. Once the tree is constructed, standard Bass-Serre theory yields that G is virtually free. This approach simplifies the existing proofs for the fundamental result of Muller and Schupp that characterizes context-free groups as f.g. virtually free groups. Our construction avoids the explicit use of Stallings' structure theorem and it is self-contained. We also give a simplified proof for an important consequence of the structure tree theory by Dicks and Dunwoody which has been stated by Thomassen and Woess. It says that a f.g. group is accessible if and only if its Cayley graph is accessible.
Recommendations
Cites work
- A characterisation of virtually free groups.
- A REMARK ABOUT COMBINGS OF GROUPS
- Accessibility and Groups of Cohomological Dimension One
- Actions of finite groups of graphs and related automorphisms of free groups
- Cutting up graphs
- Cutting up graphs revisited -- a short proof of Stallings' structure theorem.
- Finite and infinite cyclic extensions of free groups
- Graph minors. XX: Wagner's conjecture
- Graphs and groups with tree-like properties
- GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
- Groups, graphs, languages, automata, games and second-order monadic logic
- Groups, the theory of ends, and context-free languages
- Groups, trees and projective modules
- Hotz-isomorphism theorems in formal language theory
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 41228 (Why is no real title available?)
- scientific article; zbMATH DE number 3381557 (Why is no real title available?)
- Logical aspects of Cayley-graphs: the group case
- On Cayley graphs of virtually free groups.
- On groups acting on locally finite graphs
- On torsion-free groups with infinitely many ends
- The accessibility of finitely presented groups
- The co-word problem for the Higman-Thompson group is context-free
- The theory of ends, pushdown automata, and second-order logic
- Vertex-transitive graphs and accessibility
Cited in
(18)- Accessibility in transitive graphs
- Percolation on infinite graphs and isoperimetric inequalities
- On the word problem for special monoids
- Groups whose word problems are not semilinear
- The language of self-avoiding walks
- On Cayley graphs of virtually free groups.
- Vertex cuts
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Context-Free Groups and Bass–Serre Theory
- On the rank of the intersection of free subgroups in virtually free groups.
- Context-free pairs of groups. I: Context-free pairs and graphs
- scientific article; zbMATH DE number 848090 (Why is no real title available?)
- The isomorphism problem for finite extensions of free groups is in PSPACE
- Geometric characterizations of virtually free groups
- Generalizations of the Muller-Schupp theorem and tree-like inverse graphs
- Context-free pairs of groups. II: Cuts, tree sets, and random walks
- Commutative semigroups with a context-free word problem
- Tree-based language complexity of Thompson's group \(F\).
This page was built for publication: Context-free groups and their structure trees.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4923204)
