On the Non-existence of a Simple Version of the Polynomial Algorithm for Extracting the Root from the Language
DOI:
https://doi.org/10.14529/cmse240103Keywords:
formal languages, concatenation of languages, degree of the language, root of the language, polynomial algorithmsAbstract
For the usual operation of concatenation of words considered as multiplication, the concatenation of languages is obviously determined, and on the basis of the last operation, the degree of the language and the root of a given degree (if available) is determined. When describing algorithms for constructing a language that is a root of degree M from a given language, so called potential roots are of great importance: these are the words (not the languages) whose considered M-th degree is included in a given language. It is easily to show that all potential roots for a given language are constructed using a polynomial algorithm. This task, apparently, is not simplified when considering words and languages over the 1-letter alphabet, which is done in this paper. So called taboo pair of potential roots is a pair whose word concatenation is not included in the language. In previous publications on the topic of describing algorithms for extracting roots from a language, the hypothesis arose that a polynomial algorithm for extracting a root from a language can be described on the basis of considering the set of taboo pairs only, by iterating over specially described subsets of the set of potential roots. This paper shows, that such an algorithm (called “simple”) is impossible, i.e., if there is a polynomial algorithm for extracting the root from the language, then this algorithm must use some additional information.References
Melnikov B.F., Melnikova А.А. On the problems of extracting the root from a given finite language. International Journal of Open Information Technologies. 2023. Vol. 11, no. 5. P. 1–14. (in Russian)
Melnikov B.F., Korabelshchikova S.Yu., Dolgov V.N. On the task of extracting the root from the language. International Journal of Open Information Technologies. 2019. Vol. 7, no. 3. P. 1–6.
Melnikov B.F. A polynomial algorithm for constructing the optimal inverse morphism. International Journal of Open Information Technologies. 2023. Vol. 11, no. 6. P. 1–10. (in Russian)
Stockmeyer L.J. The polynomial-time hierarchy. Theoretical Computer Science. 1976. Vol. 3, no. 1. P. 1–22.
Chandra A.K., Kozen D., Stockmeyer L.J. Alternation. Journal of the ACM. 1981. Vol. 28, no. 1. P. 114–133.
Immerman N. TDescriptive Complexity. Berlin: Springer, 1999. 284 p.
Hromkovic J. Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Berlin: Springer, 2003. 323 p.
Hromkovic J. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Berlin: Springer, 2004. 547 p.
Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language. International Journal of Open Information Technologies. 2022. Vol. 10, no. 4. P. 1–9. (in Russian)
Ryabov G.G. On the quaternary coding of cubic structures. Computational methods and programming. 2009. Vol. 10, no. 3. P. 340–347. (in Russian)
Ryabov G.G. Hausdorff metric on the faces of an N-dimensional cube. Fundamental and Applied Mathematics. 2010. Vol. 16, no. 1. P. 151–155. (in Russian)
Ryabov G.G. Polymorphism of symbolic ternary matrices and genetic space of shortest K-paths in an N-cube. International Journal of Open Information Technologies. 2015. Vol. 3, no. 7. P. 1–11. (in Russian)
