Complexity of finite state Turing machine with other domain - Rajesh Kumar; Anju Jain; Rakesh Kumar (Computer Science and Information Technologies, 2026)
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 Kleene star-free unary and recursive languages accepted by the finite state Turing machine.