Compressed words and automorphisms in fully residually free groups.

DOI10.1142/S021819671000542XMaRDI QIDQ3578449zbMATH OpenFDO

Authors Jeremy Macdonald

Publication date 20 July 2010

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

automorphism groupscompressed word problemfully residually free groupslimit groups

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Residual properties and generalizations; residually finite groups (20E26) Automorphisms of infinite groups (20E36) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Automorphism groups of groups (20F28) Geometric group theory (20F65)

Abstract: We show that the compressed word problem in a finitely-generated fully residually free group (F -group) is decidable in polynomial time, and use the result to show that the word problem in the automorphism group of such a group is decidable in polynomial time.

Recommendations

• Polynomial-time word problems.
• Compressed word problems in HNN-extensions and amalgamated products
• The isomorphism problem for finitely generated fully residually free groups.
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• The Compressed Word Problem for Groups

Cites work

• Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups
• The isomorphism problem for finitely generated fully residually free groups.

Cited in

(12)

• Compression techniques in group theory
• The complexity of compressed membership problems for finite automata
• Linear estimates for solutions of quadratic equations in free groups.
• Compressed membership in automata with compressed labels
• Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Compressed decision problems in hyperbolic groups
• Logspace and compressed-word computations in nilpotent groups
• FULLY RESIDUALLY FREE GROUPS AND GRAPHS LABELED BY INFINITE WORDS
• Compressed word problems in HNN-extensions and amalgamated products
• Compressed decision problems in hyperbolic groups
• Polynomial-time word problems.

This page was built for publication: Compressed words and automorphisms in fully residually free groups.

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