检索结果-内蒙古大学图书馆

Membership problems in finite groups

JOURNAL OF ALGEBRA 2025年 675卷 23-58页

作者： Lohrey, Markus Rosowski, Andreas Zetzsche, Georg Univ Siegen Siegen Germany Max Planck Inst Software Syst Kaiserslautern Germany

We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed n >= 3, where n is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks [34], which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant HortonStrahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar. This paper is an extended version of the conference paper [31]. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// ***/licenses/by/4.0/).

关键词： algorithmic group theory Finite groups Membership problems Automata theory

来源：评论

学校读者我要写书评

暂无评论

Conjugacy in Baumslag's group, Generic Case Complexity, and Division in Power Circuits

引用

algorithmicA 2016年第4期76卷 961-988页

作者： Diekert, Volker Myasnikov, Alexei G. Weiss, Armin Univ Stuttgart FMI Univ Str 38 D-70569 Stuttgart Germany Stevens Inst Technol Dept Math Hoboken NJ 07030 USA

The conjugacy problem asks whether two words over generators of a fixed group G are conjugated, i.e., it is the problem to decide on input words x, y whether there exists z such that in G. The conjugacy problem is more difficult than the word problem, in general. We investigate the conjugacy problem for two prominent groups: the Baumslag-Solitar group and the Baumslag group (also known as Baumslag-Gersten group). The conjugacy problem in is complete for the circuit class . To the best of our knowledge is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group is an HNN-extension of . Hence, decidability of the conjugacy problem in outside the so-called "black hole" follows from Borovik et al. (Int J Algebra Comput 17(5/6):963-997, 2007). Decidability everywhere is due to Beese. Moreover, he showed exponential time for the set of elements which cannot be conjugated into (Beese 2012). Here we improve Beese's result in two directions by showing that the conjugacy problem in can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs, conjugacy in can be decided efficiently. In contrast, we show that under a plausible assumption the average case complexity of the same problem is non-elementary. Moreover, we provide a lower bound for the conjugacy problem in by reducing the divisibility problem in power circuits to the conjugacy problem in . The complexity of the divisibility problem in power circuits is an open and interesting problem in integer arithmetic. We conjecture that it cannot be solved in elementary time because we can show that it cannot be solved in elementary time by calculating modulo values in power circuits.

关键词： algorithmic group theory Power circuit Generic case complexity Divisibility problem Conjugacy problem Baumslag group

来源：评论

学校读者我要写书评

暂无评论

COMPUTING A BASIS FOR A FINITE ABELIAN P-group

引用

INFORMATION PROCESSING LETTERS 1985年第3期20卷 161-163页

作者： BEYNON, WM ILIOPOULOS, CS UNIV WARWICK DEPT COMP SCICOVENTRY CV4 7ALW MIDLANDSENGLAND

An algorithm for calculating a basis for a finite abelian p-group, given a set of generators, is described. The alternative method presented does not assume that defining relations of the p-group are known, but employs a direct recursive algorithm for devising bases of successively larger subgroups of the p-group until a basis for the p-group is reached. The algorithm is most efficient when a generating set of small size relative to the p-group is known, and is especially suited for use when a generating set for the p-group is itself being produced in a sequential manner. For computational purposes, it is assumed that every element of the p-group has a certain binary representation of length. The algorithm compares favorably with algorithms based upon decreasing the matrix of coefficients in the relations to Smith normal form.

关键词： Computational complexity algorithmic group theory

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithms for Highly Compressed Data: The Word Problem in Generalized Higman groups Is in P

引用

theory OF COMPUTING SYSTEMS 2014年第4期55卷 742-770页

作者： Laun, Juern Univ Stuttgart Inst Formale Methoden Informat D-70199 Stuttgart Germany

This paper continues the 2012 STACS contribution by Diekert, Ushakov, and the author as well as the 2012 IJAC publication by the same authors. We extend the results published there in two ways. First, we show that the data structure of power circuits can be generalized to work with arbitrary bases qa parts per thousand yen2. This results in a data structure that can hold huge integers, arising by iteratively forming powers of q. We show that the properties of power circuits known for q=2 translate to the general case. This generalization is non-trivial and additional techniques are required to preserve the time bounds of arithmetic operations that were shown for the case q=2. The extended power circuit model permits us to conduct operations in the Baumslag-Solitar group BS(1,q) as efficiently as in BS(1,2). This allows us to solve the word problem in the generalization H (4)(1,q) of Higman's group in polynomial time. The group H (4)(1,q) is an amalgamated product of four copies of the Baumslag-Solitar group BS(1,q) rather than BS(1,2) in the original group H (4)=H (4)(1,2). As a second result, we allow arbitrary numbers fa parts per thousand yen4 of copies of BS(1,q), leading to an even more generalized notion of Higman groups H (f) (1,q). We prove that the word problem of the latter can still be solved within the time bound that was shown for H (4)(1,2).

关键词： Data structures Compression algorithmic group theory Word problem

来源：评论

学校读者我要写书评

暂无评论

Subgroup Membership in GL(2,Z)

引用

theory OF COMPUTING SYSTEMS 2024年第4期68卷 1082-1107页

作者： Lohrey, Markus Univ Siegen Siegen Germany

It is shown that the subgroup membership problem for a virtually free group can be decided in polynomial time when all group elements are represented by so-called powerwords, i.e., words of the form p(1)(z1)p(2)(Z2) ... p(k)(zk). Here the pi are explicitwords over the generating set of the group and all zi are binary encoded integers. As a corollary, it follows that the subgroup membership problem for the matrix group GL(2, Z) can be decided in polynomial time when elements of GL(2, Z) are represented by matrices with binary encoded integers. For the same input representation, it also shown that one can compute in polynomial time the index of a given finitely generated subgroup of GL(2, Z).

关键词： algorithmic group theory Subgroup membership problems Algorithms for GL(2,Z)

来源：评论

学校读者我要写书评

暂无评论

Compressed decision problems in hyperbolic groups

引用

groupS GEOMETRY AND DYNAMICS 2024年第4期18卷 1233-1273页

作者： Holt, Derek Lohrey, Markus Schleimer, Saul Univ Warwick Math Inst Zeeman Bldg Coventry CV4 7AL England Univ Siegen Dept Elect Engn & Comp Sci Holderlinstr 3 D-57076 Siegen Germany

We prove that, for any hyperbolic group, the compressed word and the compressed conjugacy problems are solvable in polynomial time. As a consequence, the word problem for the (outer) automorphism group of a hyperbolic group is solvable in polynomial time. We also prove that the compressed simultaneous conjugacy and the compressed centraliser problems are solvable in polynomial time. Finally, we prove that, for any infinite hyperbolic group, the compressed knapsack problem is NP-complete.

关键词： algorithmic group theory hyperbolic groups word problem straight-line programs

来源：评论

学校读者我要写书评

暂无评论

New refiners for permutation group search

引用

JOURNAL OF SYMBOLIC COMPUTATION 2019年 92卷 70-92页

作者： Jefferson, Christopher Pfeiffer, Markus Waldecker, Rebecca Univ St Andrews Sch Comp Sci St Andrews KY16 9SX Fife Scotland Martin Luther Univ Halle Wittenberg Inst Math D-06099 Halle Germany

Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack - in some cases by several orders of magnitude. (C) 2018 The Authors. Published by Elsevier Ltd.

关键词： Backtrack search Refiners Permutation groups algorithmic group theory Computational algebra Partition backtrack

来源：评论

学校读者我要写书评

暂无评论

Special polycyclic generating sequences for finite soluble groups

引用

JOURNAL OF SYMBOLIC COMPUTATION 2004年第5期38卷 1445-1460页

作者： Cannon, JJ Eick, B Leedham-Green, CR Tech Univ Carolo Wilhelmina Braunschweig Inst Computat Math D-38106 Braunschweig Germany Univ Sydney Sch Math & Stat Sydney NSW 2006 Australia Univ London Queen Mary & Westfield Coll Sch Math Sci London E1 4NS England

Polycyclic generating sequences are known to be a powerful tool in the design of practical and efficient algorithms for computing in finite soluble groups. Here we describe a further development: the so-called special polycyclic generating sequences. We give an overview of their properties and introduce a practical algorithm for determining a special polycyclic generating sequence in a given finite soluble group. (C) 2004 Elsevier Ltd. All rights reserved.

关键词： soluble groups maximal subgroups Hall subgroups algorithmic group theory

来源：评论

学校读者我要写书评

暂无评论

Logspace computations in graph products

引用

JOURNAL OF SYMBOLIC COMPUTATION 2016年 75卷 94-109页

作者： Diekert, Volker Kausch, Jonathan Univ Stuttgart FMI Univ Str 38 D-70569 Stuttgart Germany

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. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： algorithmic group theory Graph products Logspace complexity Word problem Geodesics Conjugacy problem

来源：评论

学校读者我要写书评

暂无评论

Cyclic rewriting and conjugacy problems

引用

groupS COMPLEXITY CRYPTOLOGY 2012年第2期4卷 321-355页

作者： Diekert, Volker Duncan, Andrew Myasnikov, Alexei G. Univ Stuttgart Univ Str 38 D-70569 Stuttgart Germany Newcastle Univ Newcastle Upon Tyne NE1 7RU Tyne & Wear England Stevens Inst Technol Hoboken NJ 07030 USA

Cyclic words are equivalence classes of cyclic permutations of ordinary words. When a group is given by a rewriting relation, a rewriting system on cyclic words is induced, which is used to construct algorithms to find minimal length elements of conjugacy classes in the group. These techniques are applied to the universal groups of Stallings pre-groups and in particular to free products with amalgamation, HNN- extensions and virtually free groups, to yield simple and intuitive algorithms and proofs of conjugacy criteria.

关键词： algorithmic group theory rewriting system conjugacy problem HNN-extension free product with amalgamation Stallings pregroup

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：