INTRODUCING PQI-OPERATOR IN THEORY OF COMPUTATIONAL COMPLEXITY

Authors

Keywords:

computational complexity, operator, theoretical computer science, subset construction, finite state automatons.

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.

Downloads

Download data is not yet available.

Author Biography

Mirzakhmet Syzdykov, al-Farabi Kazakh National University, Almaty, Kazakhstan

Born 11/09/84. 2006-2009, aspirant at Institute of Problems in Informatics and Control

Downloads

Published

2022-09-30

How to Cite

Syzdykov, M. (2022). INTRODUCING PQI-OPERATOR IN THEORY OF COMPUTATIONAL COMPLEXITY. ADVANCED TECHNOLOGIES AND COMPUTER SCIENCE, 1(3), 4–9. Retrieved from https://atcs.iict.kz/index.php/atcs/article/view/69

Issue

Section

Applied mathematics, computer science and control theory