A specialized completion procedure for monadic string-rewriting systems presenting groups

Abstract

Based on a simplified test for determining whether a finite monadic string-rewriting system R presenting a group is confluent on the equivalence class of the unity, a procedure for completing a system of this form on [e]R is derived. The completion procedure transforms monadic presentations in monadic ones by adding monadic rules which are extracted from appropriate infinite regular sets in polynomial time. The correctness and completeness of this procedure are shown.