INTRODUCING PQI-OPERATOR IN THEORY OF COMPUTATIONAL COMPLEXITY

Abstract

In this article we describe the notion of PQI-operator used before in application role for implementing extended finite state automatons within the subset construction; we give precise definition of this operator and prove important complexity theorems according to the model provided and prior work; the presented operation method can be used for the estimation of the overridden complexity as per automatons constructed through modified subset construction which was well studied before. The complexity, thus, can be of different type according to the classification which was presented earlier in this research of the decidability of complex algorithms which are impractical due to the state explosion, for example, in Rabin-Scott subset construction. These algorithms' complexity can be the type of factorial also. We will show that there exists a PQI-operator followed from the approach presented in the cycle of these works, thus, this work can be seen as the continuation of the study of the theory of automatons and state complexity.