On the problems of extracting the root from a given finite language
Abstract
The article considers finite languages only. Based on the standard definition of the product (concatenation), the non-negative degree of the language is introduced. Root extraction is the inverse operation to it, and it can be defined in several different ways. Despite the simplicity of the formulation of the problem, the authors could not find any description of it in the literature (as well as on the Internet), including even its formulation. Despite this, we believe that all the material of the paper (including the proven theorem) about a possible change in the root-answer it is very easy, and it is puzzling that there are no formulations of such tasks in the monographs known to the authors. Most of the material in this paper is devoted to the simplest version of the formulation, i.e., the root of the 2-th degree for the 1-letter alphabet; but many of the topics of the paper are generalized to more complex cases. Apparently, for a possible future description of a polynomial solution algorithm, at least one of the described statements of the root extraction tasks first needs to really analyze in detail such a special case, that is: either describe the necessary polynomial algorithm, or, conversely, show that the problem belongs to the class of NPcomplete problems. Thus, in this paper we do not propose a polynomial algorithm for the considered problems; however, the models described here should help in constructing appropriate heuristic algorithms for solving them. A detailed description of the possible further application of such heuristic algorithms is beyond the scope of this article, but several arguments about such a possible application can be carried out already now. Firstly, the possibility of using such algorithms in cryptography and cryptanalysis is quite obvious. Secondly, even if there is a polynomial algorithm for the considered root extraction problem, it seems to be quite complex, and should be called a “intractable” or a “hard problem”. Thirdly, the considered problem is easily reduced to an NP-complete problem from the field of graph theory, i.e. the problem of finding a clique; at the same time, the opposite information has not been proven; we also mention the problem of set covering.
Full Text:
PDF (Russian)References
Salomaa A. Jewels of Formal Language Theory. Computer Science Press, Rockville, Maryland (1981). – 144 p.
Melnikov B., Korabelshchikova S., Dolgov V. 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. 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).
Ginsburg S. The Mathematical Theory of Context-free Languages. NY: McGraw-Hill Ed. – 1966. – 245 p.
Aho A., Ullman J. The Theory of Parsing, Translation, and Compiling. Vol. 1: Parsing. NJ: Prentice Hall, 1972. – 560 p.
Hopcroft J., Motwani R., Ullman J. Introduction to Automata Theory, Languages, and Computation. Massachusetts, Addison-Wesley Publishing Company Reading. – 2006. – 550 p.
Hromkovič J. Theoretical Computer Science. Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Berlin, Springer. – 2003. – 321 p.
Garey M., Johnson D. Computers and Intractability. USA: W. H. Freeman and Company. – 1979. – 338 p.
Eremeev A., Zaozerskaya L., Kolokolov A. The problem of covering a set: complexity, algorithms, experimental studies // Discrete analysis and operations research, ser. 2. – 2000. – Vol. 7. No. 2. – P. 22–46. (In Russian.)
Kameda T., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. – 1970. – Vol. C-19, No. 7. – P. 617–627.
Jiang T., Ravikumar B. Minimal NFA problems are hard. SIAM Journal on Computing. 1993, Vol. 22, No. 6, P. 1117–1141.
Melnikov B. Subclasses of the context-free languages class (monograph). – Moscow, Moscow State University Ed. – 1995. – 174 p. – ISBN 5-211-03448-1. (in Russian).
Melnikov B., Vakhitova A. Some more on the finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Computational and Applied Mathematics). – 1998. – Vol. 5, No. 3. – P. 495–505.
Melnikov B. A new algorithm of the state-minimization for the nondeterministic finite automata. The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 1999, Vol. 6, No. 2. – P. 277–290.
Polák L. Minimalizations of NFA using the universal automaton // International Journal of Foundation of Computer Science. – 2005. – Vol. 16, No. 5. – P. 999–1010.
Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata. Amsterdam University Press. – 2008. – P. 457–504.
Hromkovič J., Petersen H., Schnitger G. On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s. Theoretical Computer Science. 2009. – No. 410. – P. 2972–2981.
Yo-Sub Han. State elimination heuristics for short regular expressions. Fundamenta Informaticae. 2013. – No. 128. – P. 445–462.
Dolgov V., Melnikov B. On the automatic construction algorithms of Waterloo-like finite automata based on complete automata // Heuristic algorithms and distributed computing. – 2014. – Vol. 1. No. 4. – P. 24–45 (in Russian).
Melnikov B. Regular languages and nondeterministic finite automata (monograph). – Moscow, Russian Social State University Ed. – 2018. – 179 p. – ISBN 978-5-7139-1355- 7. (in Russian).
Harary F. Graph theory // Massachusetts: Addison-Wesley Publ. – 1969. – 274 p.
Diestel R. Graph theory // Heidelberg: Springer-Verlag, 1997. – 358 p.
Gera R., Hedetniemi S., Larson C. (Eds.) Graph Theory. Favorite Conjectures and Open Problems – 1. Berlin: Springer, 2016 – 291 p.
Karpov D. Graph theory // Saint Petersburg: Publishing House of the St. Petersburg Branch Mathematical Institute named after V. A. Steklov of Russian Academy of Sciences, 2017. – 482 p. (in Russian)
Gera R., Hedetniemi S., Larson C. (Eds.) Graph Theory. Favorite Conjectures and Open Problems – 2. Berlin: Springer, 2018. – 281 p.
Needham M., Hodler E. Graph Algorithms. Practical Examples in Apache Spark and Neo4j. Berlin: O’Reilly Media, Inc. – 2019. – 300 p
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162