ISSN:
1432-0622
Keywords:
Polyclinic groups
;
Context-free groups
;
Subgroups
;
Prefix-rewriting systems
;
String-rewriting systems
;
λ-confluence
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract Algorithms for solving uniform decision problems for algebraic structures crucially depend on the chosen finite presentations for the structures under consideration. Rewriting techniques have been used very successfully to solve uniform decision problems, when the presentations considered involve finite, noetherian, and (λ)-confluent rewriting systems. Whenever the class of algebraic structures considered is closed under the operation of taking finitely generated substructures, then the algorithms for solving the uniform decision problems can be applied to the substructures as well. However, since these algorithms depend on the form of the presentations, this involves the task of constructing a presentation of a certain form for a substructure given a presentation of this form for the structure itself and a finite set of generating elements for the substructure. This problem, which has received a lot of attention in algebra, is here investigated from an algorithmic point of view. The structures considered are the following two classes of groups, which have been studied extensively before: the polycyclic groups and the context-free groups. Finitely generated context-free groups can be presented by finite, monadic, and λ-confluent string-rewriting systems. Due to their nice algorithmic properties these systems provide a way to effectively solve many decision problems for context-free groups. Since finitely generated subgroups of context-free groups are again contextfree, they can be presented in the same way. Here we describe a process that, from a finite, monadic, and λ-confluent string-rewriting system presenting a context-free groupG and a finite subsetU ofG, determines a presentation of this form for the subgroup 〈U〉 ofG that is generated byU. For finitely presented polycyclic groups we obtain an analogous result, when we use finite confluent PCP2-presentations to describe these groups.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01225643
Permalink
