Computing Presentations for Subgroups of Polycyclic Groups and of Context-Free Groups

Abstract

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 context-free, 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 group G and a finite subset U of G, determines a presentation of this form for the subgroup 〈U〉 of G that is generated by U. For finitely presented polycyclic groups we obtain an analogous result, when we use finite confluent PCP2-presentations to describe these groups.