DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP

DOI10.1070/IM1985v025n01ABEH001269zbMath0578.20001OpenAlexW2076844127MaRDI QIDQ3699893

Gennady S. Makanin

Publication date: 1985

Published in: Mathematics of the USSR-Izvestiya (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/im1985v025n01abeh001269

zbMATH Keywords

universal theoryfree groups of finite rankpositive theorysolvability of equationspositive formulae on free groups

Mathematics Subject Classification ID

Model-theoretic algebra (03C60) Generators, relations, and presentations of groups (20F05) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Axiomatics and elementary properties of groups (20A05) Basic properties of first-order languages and structures (03C07) Metamathematical considerations in group theory (20A10)

Related Items (36)

The Diophantine problem in the classical matrix groups ⋮ Algorithmic undecidability of compatibility problem for equations in free groups: explicit equations with one commutator-type constraint ⋮ Finite approximation and commutators in free groups. ⋮ On some algorithmic problems for groups and monoids ⋮ Diophantine geometry over groups. III: Rigid and solid solutions. ⋮ Implicit function theorem over free groups. ⋮ Elementary theory of free non-abelian groups. ⋮ On the studies of Gennadii Semënovich Makanin on algorithmic questions of the theory of groups and semigroups ⋮ The isomorphism problem for finitely generated fully residually free groups. ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Word equations in the context of string solving ⋮ Existential questions in (relatively) hyperbolic groups. ⋮ Generalizations of free groups: some questions ⋮ The word matching problem is undecidable for finite special string-rewriting systems that are confluent ⋮ Makanin's algorithm is not primitive recursive ⋮ Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups ⋮ Unnamed Item ⋮ More Than 1700 Years of Word Equations ⋮ Ideals of equations for elements in a free group and context-free languages ⋮ Investigations on equations in a free group ⋮ An analysis of Makanin's algorithm deciding solvability of equations in free groups ⋮ Algebraic and logical aspects of unification ⋮ ∀-free metabelian groups ⋮ The complexity of verbal languages over groups ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Picture-hanging puzzles ⋮ Explicit test sets for iterated morphisms in free monoids and metabelian groups ⋮ Logical aspects of Cayley-graphs: the group case ⋮ On systems of word equations over three unknowns with at most six occurrences of one of the unknowns ⋮ Extending free pregroups with lower bounds ⋮ Seven lectures on universal algebraic geometry ⋮ Unnamed Item ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ The non-parametrizability of the word equation \(xyz=zvx\): a short proof ⋮ Algebraic geometry in varieties of algebras with the given algebra of constants ⋮ Algebraic geometry over groups. I: Algebraic sets and ideal theory

This page was built for publication: DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP