n-level rewriting systems (Q1084855)

It is well known that a monoid which is presented by a finite complete rewriting system has a decidable word problem. On the other hand, the problem whether each finitely presentable recursive monoid can be presented by a finite complete rewriting system is still unsolved. It is conjectured that this is not always possible. By generalizing the rewriting systems to the n-level rewriting systems it is shown that exactly the finitely presentable recursive monoids can be presented by finite complete 2-level rewriting systems.