Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinsky machines and algorithmic problems
243
0
0.0
(
0
)
Authors
Mark Sapir
Ask ChatGPT about the research
No Arabic abstract
This is a survey of using Minsky machines to study algorithmic problems in semigroups, groups and other algebraic systems.
rate research
Read More
In this paper we consider several classical and novel algorithmic problems for right-angled Artin groups, some of which are closely related to graph theoretic problems, and study their computational complexity. We study these problems with a view towards applications to cryptography.
Every rotationless outer automorphism of a finite rank free group is represented by a particularly useful relative train track map called a CT. The main result of this paper is that the constructions of CTs can be made algorithmic. A key step in our argument is proving that it is algorithmic to check if an inclusion of one invariant free factor system in another is reduced. Several applications are included, as well as algorithmic constructions for relative train track maps in the general case.
In this article, we study connections between representation theory and efficient solutions to the conjugacy problem on finitely generated groups. The main focus is on the conjugacy problem in conjugacy separable groups, where we measure efficiency in terms of the size of the quotients required to distinguish a distinct pair of conjugacy classes.
We investigate a conjecture about stabilisation of deficiency in finite index subgroups and relate it to the D2 Problem of C.T.C. Wall and the Relation Gap problem. We verify the pro-$p$ version of the conjecture, as well as its higher dimensional abstract analogues.
For every Turing machine, we construct an automaton group that simulates it. Precisely, starting from an initial configuration of the Turing machine, we explicitly construct an element of the group such that the Turing machine stops if, and only if, this element is of finite order.If the Turing machine is universal, the corresponding automaton group has an undecidable order problem. This solves a problem raised by Grigorchuk.The above group also has an undecidable Engel problem: there is no algorithm that, given g, h in the group, decides whether there exists an integer n such that the n-iterated commutator [...[[g,h],h],...,h]$ is the identity or not. This solves a problem raised by Bartholdi.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
