BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that non-abelian free groups of finite rank at least 3 or of countable rank are not ∀-homogeneous. We answer three open questions from Kharlampovich, Myasnikov, and Sklinos regarding whether free groups, finitely generated elementary free groups, and non-abelian limit groups form special kinds of Fraïssé classes in which embeddings must preserve ∀-formulas. We also provide interesting examples of countable non-finitely generated elementary free groups.
The aim of this short note is to provide a proof of the decidability of the generalized membership problem for relatively quasi-convex subgroups of finitely presented relatively hyperbolic groups, under some reasonably mild conditions on the peripheral structure of these groups. These hypotheses are satisfied, in particular, by toral relatively hyperbolic groups.
We show that the Diophantine problem(decidability of equations) is undecidable in free associative algebras over any field and in the group algebras over any field of a wide variety of torsion free groups, including toral relatively hyperbolic groups, right angled Artin groups, commutative transitive groups, the fundamental groups of various graph groups, etc.
This note provides a brief guide to the current state of the literature on Tarski's problems with emphasis on features that distinguish the approach based on combinatorial and algorithmic group theory from the topological approach to Tarski's problem. We use this note to provide corrections to some typos and to address some misconceptions from the recent report by Z. Sela about the relations between the concepts and results in the approaches to the Tarski problems. We were forced to read Sela's papers to be able to address some of his comments, and found errors in his papers 6, 3 and 4 on Diophantine Geometry published in GAFA and Israel J. Math. which we mention in Section 4. His proceedings of the ICM 2002 paper also contains wrong Theorem 6 (to make it correct one has to change the definition of non-elementary hyperbolic ω-residually free towers to make them equivalent to our coordinate groups of regular NTQ systems.)
We show that every group with free Zn-length function is CAT(0).
In this paper we survey recent developments in the theory of groups acting on Λ-trees. We are trying to unify all significant methods and techniques, both classical and recently developed, in an attempt to present various faces of the theory and to show how these methods can be used to solve major problems about finitely presented Λ-free groups. Besides surveying results known up to date we draw many new corollaries concerning structural and algorithmic properties of such groups.
For any torsion-free hyperbolic group Γ and any group G that is fully residually Γ, we construct algorithmically a finite collection of homomorphisms from G to groups obtained from Γ by extensions of centralizers, at least one of which is injective. When G is residually Γ, this gives a effective embedding of G into a direct product of such groups. We also give an algorithmic construction of a diagram encoding the set of homomorphisms from a given finitely presented group to Γ.
The paper is a part of an ongoing program which aims to show that the existential theory in free groups (hyperbolic groups or even toral relatively hyperbolic) is NP-complete. For that we study compression of solutions with straight-line programs (SLPs) as suggested originally by Plandowski and Rytter in the context of a single word equation. We review some basic results on SLPs and give full proofs in order to keep this fundamental part of the program self-contained. Next we study systems of equations with constraints in free groups and more generally in free products of abelian groups. We show how to compress minimal solutions with extended Parikh-constraints. This type of constraints allows to express semi linear conditions as e.g. alphabetic information. The result relies on some combinatorial analysis and has not been shown elsewhere. We show similar compression results for Boolean formula of equations over a torsion-free δ-hyperbolic group. The situation is much more delicate than in free groups. As byproduct we improve the estimation of the "capacity" constant used by Rips and Sela in their paper "Canonical representatives and equations in hyperbolic groups" from a double-exponential bound in δ to some single-exponential bound. The final section shows compression results for toral relatively hyperbolic group using the work of Dahmani: We show that given a system of equations over a fixed toral relatively hyperbolic group, for every solution of length N there is an SLP for another solution such that the size of the SLP is bounded by some polynomial p(s+logN) where s is the size of the system.
We prove that there is an algorithm to determine whether a tuple of elements in a toral relatively hyperbolic group G is in the automorphic orbit of the other tuple.
We give a description of definable sets P=(p1,...,pm) in a free non-abelian group F and in a torsion-free non-elementary hyperbolic group G that follows from our work on the Tarski problems. This answers Malcev's question for F. As a corollary we show that proper non-cyclic subgroups of F and G are not definable and prove Bestvina and Feighn's result that definable subsets P=(p) in a free group are either negligible or co-negligible in their terminology.
In this paper we introduce the concept of a Cayley graph automatic group (CGA group or graph automatic group, for short) which generalizes the standard notion of an automatic group. Like the usual automatic groups graph automatic ones enjoy many nice properties: these group are invariant under the change of generators, they are closed under direct and free products, certain types of amalgamated products, and finite extensions. Furthermore, the Word Problem in graph automatic groups is decidable in quadratic time. However, the class of graph automatic groups is much wider then the class of automatic groups. For example, we prove that all finitely generated 2-nilpotent groups and Baumslag-Solitar groups B(1,n) are graph automatic, as well as many other metabelian groups.
We prove that in a free group the length of the value of each variable in a minimal solution of a standard quadratic equation is bounded by 2s for orientable equation and by 12s4 for non-orientable equation, where s is the sum of the lengths of the coefficients
In this paper we prove Implicit Function Theorems (IFT) for algebraic varieties defined by regular quadratic equations and, more generally, regular NTQ systems over free groups. In the model theoretic language these results state the existence of very simple Skolem functions for particular ∀∃-formulas over free groups. We construct these functions effectively. In non-effective form IFT first appeared in \cite{Imp}. From algebraic geometry view-point IFT can be described as lifting solutions of equations into generic points of algebraic varieties. Moreover, we show that the converse is also true, i.e., IFT holds only for algebraic varieties defined by regular NTQ systems. This implies that if a finitely generated group H is ∀∃-equivalent to a free non-abelian group then H is isomorphic to the coordinate group of a regular NTQ system.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.