A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
From MaRDI portal
Publication:3430309
Free nonabelian groups (20E05) Subgroup theorems; subgroup growth (20E07) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Graph theory (including graph drawing) in computer science (68R10)
Abstract: We show that for a fixed free group F and an arbitrary finitely generated subgroup H (as given above) we can perform the Stalling's folding process in time O(N log^*(N)), where N is the sum of the word lengths of the given generators of H.
Recommendations
- Efficient folding algorithms for convex polyhedra
- Stamp foldings, semi-meanders, and open meanders: fast generation algorithms
- A Direct Method for Computing Higher Order Folds
- scientific article; zbMATH DE number 1629824
- Algorithmic folding complexity
- Algorithmic folding complexity
- An improvement of McMillan's unfolding algorithm
Cites work
Cited in
(32)- Generalized primitivity of labeled digraphs
- An algorithmic study of manufacturing paperclips and other folded structures.
- State graphs and fibered state surfaces
- Conjugacy search problem and the Andrews-Curtis conjecture
- Efficient algorithm for box folding
- Stallings graphs for quasi-convex subgroups
- Double cosets in free groups.
- Non-commutative lattice problems
- Random van Kampen diagrams and algorithmic problems in groups.
- Generic properties of subgroups of free groups and finite presentations
- STALLINGS FOLDINGS AND SUBGROUPS OF AMALGAMS OF FINITE GROUPS
- ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
- On an algorithm to decide whether a free group is a free factor of another
- RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP
- READING OFF KUROSH DECOMPOSITIONS
- FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
- Statistical properties of subgroups of free groups.
- On the Generalized Membership Problem in Relatively Hyperbolic Groups
- Compressed decision problems in hyperbolic groups
- A list of applications of Stallings automata
- Efficient Algorithm for Box Folding
- Search problems in groups and branching processes.
- On Substitutions Preserving Their Return Sets
- On the lattice of subgroups of a free group: complements and rank
- Dependence over subgroups of free groups
- The central tree property and algorithmic problems on subgroups of free groups
- Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
- A fast algorithm for Stallings foldings over virtually free groups
- A first taste of MeSCaL, a tool for solving membership problems for regular languages
- Subgroup membership in GL\((2,\mathbb{Z})\)
- Finite automata for Schreier graphs of virtually free groups
- The monomorphism problem in free groups.
This page was built for publication: A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3430309)
