n-level rewriting systems

AbstractIt is well known that a monoid which is presented by a finite complete rewriting system has a decidable work 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 generalising 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