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...
详细信息
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).
The conjugacy problem is the following question: given two words x, y over generators of a fixed group G, decide whether x and y are conjugated, i.e., whether there exists some z such that zxz(-1) = y in G. The conjug...
详细信息
ISBN:
(纸本)9783642544231
The conjugacy problem is the following question: given two words x, y over generators of a fixed group G, decide whether x and y are conjugated, i.e., whether there exists some z such that zxz(-1) = y 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 BS1,2 and the Baumslag(-Gersten) group G(1,2). The conjugacy problem in BS1,2 is TC0-complete. To the best of our knowledge BS1,2 is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group G(1,2) is an HNN-extension of BS1,2 and its conjugacy problem is decidable G(1,2) by a result of Beese (2012). Here we show that conjugacy in G(1,2) can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs conjugacy in G(1,2) 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 G(1,2) by reducing the division problem in power circuits to the conjugacy problem in G(1,2). The complexity of the division problem in power circuits is an open and interesting problem in integer arithmetic.
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 fin...
详细信息
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.
Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the...
详细信息
ISBN:
(纸本)9783939897354
Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is is decidable in polynomial time. Before that the best known upper bound was non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic group theory: 1. We define a modified reduction procedure on power circuits which runs in quadratic time thereby improving the known cubic time complexity. 2. We improve the complexity of the Word Problem for the Baumslag group to cubic time thereby providing the first practical algorithm for that problem. 3. The Word Problem of Higman's group is decidable in polynomial time. It is due to the last result that we were forced to advance the theory of power circuits.
Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the...
详细信息
Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is in P. Before that the best known upper bound was non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic algebra and algorithmic group theory: (1) We define a modified reduction procedure on power circuits which runs in quadratic time, thereby improving the known cubic time complexity. The improvement is crucial for our other results. (2) We improve the complexity of the Word Problem for the Baumslag group to cubic time, thereby providing the first practical algorithm for that problem. (The algorithm has been implemented and is available in the CRAG library.) (3) The main result is that the Word Problem of Higman's group is decidable in polynomial time. The situation for Higman's group is more complicated than for the Baumslag group and forced us to advance the theory of power circuits.
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 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.
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 emplo...
详细信息
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.
暂无评论