错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A semigroup with linearithmic Dehn function

  • Roman Repeev

摘要

It is known that no finitely presented group has the Dehn function asymptotically strictly between linear and quadratic functions. We present an example of a semigroup whose Dehn function is equivalent to \(n \log n\) n log n , thus strictly inside the said gap. The example is obtained by symmetrizing the rewriting rules of a particular semi-Thue system, which has the derivational complexity function \(n \log n\) n log n .