Complexity of finite state Turing machine with other domain

Rajesh Kumar (Chhaju Ram Memorial Jat College)
Anju Jain (Government College)
Rakesh Kumar (Kurukshetra University)

Computer Science and Information Technologies
Vol 7, No 2: July 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.