On deciding the confluence of a finite string-rewriting system on a given congruence class

摘要

In general it is undecidable whether or not a given finite string-rewriting system R is confluent on a given congruence class [w]R, even when only length-reducing systems are considered. However, for finite monadic string-rewriting systems this problem becomes decidable in double exponential time. For certain subclasses of monadic string-rewriting systems algorithms of lower complexity are obtained for solving this problem.