The derivational complexity of string rewriting systems

AbstractWe study the derivational complexities of string rewriting systems. We discuss the following fundamental question: which functions can be derivational complexities of terminating finite string rewriting systems? They are recursive, but for any recursive function, there is a derivational complexity larger than it. We relate them to the time functions of Turing machines. In particular, we show that the functions nα(α>2) and αn(α>1) for a real number α are equivalent to the derivational complexity of some finite string rewriting systems if the computational complexity of α is relatively low (for example, α is rational, algebraic, π or e). On the other hand, they cannot be equivalent to any derivational complexities if the complexity of α is high