Solving one-variable equations in free groups
From MaRDI portal
Publication:3619537
DOI10.1515/JGT.2008.080zbMath1196.20051arXivmath/0607176MaRDI 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
cancellation; free groups; formal languages; solution sets; polynomial-time algorithms; one-variable equations; parametric words
68W30: Symbolic computation and algebraic computation
68R15: Combinatorics on words
20E05: Free nonabelian groups
20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F70: Algebraic geometry over groups; equations over groups
Related Items
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., Random 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