اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMinsky machines and algorithmic problems
188
0
0.0
(
0
)
تأليف
Mark Sapir
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This is a survey of using Minsky machines to study algorithmic problems in semigroups, groups and other algebraic systems.
قيم البحث
اقرأ أيضاً
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 i
n 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
