Finite automata for Schreier graphs of virtually free groups

DOI10.1515/JGTH-2015-0028MaRDI QIDQ905401zbMATH OpenOpenAlexFDO

Authors Pedro V. Silva, Xaro Soler-Escrivà, Enric Ventura Capell

Publication date 19 January 2016

Published in Journal of Group Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.5709, http://hdl.handle.net/2117/83851

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: The Stallings construction for finitely generated subgroups of free groups is generalized by introducing the concept of Stallings section, which allows an eficient computation of the core of a Schreier graph based on edge folding. It is proved that those groups admitting Stallings sections are precisely finitely generated virtually free groups, through a constructive approach based on Bass-Serre theory. Complexity issues and applications are also discussed.

Recommendations

• STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE GROUPS
• scientific article; zbMATH DE number 7658489
• Stallings graphs for quasi-convex subgroups
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• A list of applications of Stallings automata

Cited in

(13)

• Stallings graphs for quasi-convex subgroups
• Statistics of subgroups of the modular group
• Geometric characterizations of virtually free groups
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• On the transition monoid of the Stallings automaton of a subgroup of a free group
• Stallings automata for free-times-abelian groups: intersections and index
• Vertex separators, chordality and virtually free groups
• scientific article; zbMATH DE number 7658489 (Why is no real title available?)
• A list of applications of Stallings automata
• On the Generalized Membership Problem in Relatively Hyperbolic Groups
• STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE GROUPS
• A fast algorithm for Stallings foldings over virtually free groups
• Stallings foldings and subgroups of free groups

This page was built for publication: Finite automata for Schreier graphs of virtually free groups

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