Complexity of finite state Turing machine with other domain

Abstract

In this paper, the authors investigate and discussed the non-deterministic state complexity of certain operations on finite state Turing machine on other domain which includes partial function and natural function over an alphabet set Σ∗. It is found that in some boolean operations on said domains, the state complexity reaches up to upper bound O(√n!). This result is complement for the operation on Kleen star-free unary and recursive languages accepted by the finite state Turing machine.