Finite automata for Schreier graphs of virtually free groups

DOI10.1515/JGTH-2015-0028zbMATH Open1432.20024arXiv1112.5709OpenAlexW2143834829MaRDI QIDQ905401FDOQ905401

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)

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.

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

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

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)

Cited In (13)

• A list of applications of Stallings automata
• Stallings graphs for quasi-convex subgroups
• Title not available (Why is that?)
• On the transition monoid of the Stallings automaton of a subgroup of a free group
• Geometric characterizations of virtually free groups
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• Stallings automata for free-times-abelian groups: intersections and index
• Statistics of subgroups of the modular group
• On the Generalized Membership Problem in Relatively Hyperbolic Groups
• Vertex separators, chordality and virtually free groups
• A fast algorithm for Stallings foldings over virtually free groups
• Stallings foldings and subgroups of free groups
• STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE 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)