Operational Calculus of Modified Subset Construction



subset construction, extended regular expressions, modification, operations, calculus


We present the continuation of studying Extended Regular Expression (ERE) on the view of modified subset construction within the overridden operators like intersection, subtraction, and re-written complement. As before we have stated that in this case the complexity has a decreasing nature and tendency. We will give the strict definition of the operational part of this modified subset construction which is due to Rabin and Scott. The complexity of algorithm remains a magnitude less than NP-hard problems for which we have given the strict proof of equivalence in the prior work, so this work continues the studying of the comparable proof for a variety of problems to be computationally complex, however, explainable in terms of unified approach like operational calculus. In this calculus the general points of research are given to the representation of modified subset construction with at least two operands which are to be computed by subset construction and in terms of complexity of the effective algorithm they are computed using modified subset construction.


Download data is not yet available.

Author Biography

Mirzakhmet Syzdykov, Satbayev University

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




How to Cite

Syzdykov, M. (2023). Operational Calculus of Modified Subset Construction. ADVANCED TECHNOLOGIES AND COMPUTER SCIENCE, 1(3), 4–8. Retrieved from https://atcs.iict.kz/index.php/atcs/article/view/132



Applied mathematics, computer science and control theory

Most read articles by the same author(s)

1 2 > >>