Solving one-variable equations in free groups

DOI10.1515/JGT.2008.080zbMath1196.20051arXivmath/0607176OpenAlexW2104853817MaRDI QIDQ3619537

Robert H. Gilman, Dimitri Bormotov, Alexei G. Myasnikov

Publication date: 8 April 2009

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

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

zbMATH Keywords

cancellationfree groupsformal languagessolution setspolynomial-time algorithmsone-variable equationsparametric words

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Combinatorics on words (68R15) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70)

Related Items

Random equations in free groups, Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint, Equations over free inverse monoids with idempotent variables, A polynomial bound on solutions of quadratic equations in free groups., On systems of equations over free partially commutative groups

Cites Work

• Discriminating completions of hyperbolic groups
• Elementary theory of free non-abelian groups.
• The isomorphism problem for finitely generated fully residually free groups.
• Makanin's algorithm is not primitive recursive
• Algebraic geometry over groups. I: Algebraic sets and ideal theory
• Irreducible affine varieties over a free group. I: Irreducibility of quadratic equations and Nullstellensatz
• Algebraic geometry over groups. II: Logical foundations
• Implicit function theorem over free groups.
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• EQUATIONS IN A FREE GROUP
• Satisfiability of word equations with constants is in PSPACE
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• Equations in Free Groups
• Groups With Parametric Exponents
• EXPONENTIAL GROUPS 2: EXTENSIONS OF CENTRALIZERS AND TENSOR COMPLETION OF CSA-GROUPS
• Equations in free groups with one variable. I
• Uniqueness Theorems for Periodic Functions
• One-Variable Equations in Free Groups