کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
401328 675339 2016 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Logspace computations in graph products
ترجمه فارسی عنوان
محاسبات لاگ اسپیس در محصولات نمودار
کلمات کلیدی
نظریه گروه الگوریتمی؛ محصولات نمودار؛ پیچیدگی لاگ اسپیس؛ مشکل واژه؛ ژئودزیک؛
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی

We consider three important and well-studied algorithmic problems in group theory: the word, geodesic, and conjugacy problem. We show transfer results from individual groups to graph products. We concentrate on logspace complexity because the challenge is actually in small complexity classes, only. The most difficult transfer result is for the conjugacy problem. We have a general result for graph products, but even in the special case of a graph group the result is new. Graph groups are closely linked to the theory of Mazurkiewicz traces which form an algebraic model for concurrent processes. Our proofs are combinatorial and based on well-known concepts in trace theory. We also use rewriting techniques over traces. For the group-theoretical part we apply Bass–Serre theory. But as we need explicit formulae and as we design concrete algorithms all our group-theoretical calculations are completely explicit and accessible to non-specialists.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Symbolic Computation - Volume 75, July–August 2016, Pages 94–109
نویسندگان
, ,