A polynomial algorithm for constructing the optimal inverse morphism

Boris Melnikov

Abstract


In this paper, we continue the theme of some our previous works. In this topic, we consider two similar problems of the formal languages theory: the problem of extracting the root of a given degree and the problem of constructing an optimal inverse morphism, where optimality can be defined as the length of the maximum word of a language that is an inverse morphic image. Instead of considering all subsets of the set of so-called potential roots, which always leads to exponential algorithms, we obtained some various polynomial algorithms in these publications. In order to formulate the second of these problems in a way convenient for constructing polynomial algorithms, we have considered some equivalent versions of the special hypothesis of the formal languages theory in previous papers. One of its equivalent formulations can be expressed as follows. For two finite languages not containing the empty word, we can consider the necessary and sufficient condition that the iteration of any of both languages belongs to the set of prefixes of the other language, and write it as follows. There is some new alphabet, different from the alphabet over which the source languages are set, and above this alphabet there are two maximum prefix codes (generally speaking, different ones) and two languages containing these maximum prefix codes as subsets. In addition, there is some special morphism, and the source languages should be formed by applying this morphism to the languages containing these maximal prefix codes as subsets. In this paper, we show that when this hypothesis is fulfilled, a polynomial algorithm for constructing an optimal inverse morphism is possible. Moreover, simplifying the situation a little, we can say that such an algorithm is a special combination of several polynomial algorithms considered in our previous papers, or simple modifications of such algorithms.


Full Text:

PDF (Russian)

References


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., Melnikova A. A polynomial algorithm for checking the fulfillment of the condition of the morphic image of the extended maximal prefix code // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 12. – P. 1–9 (in Russian).

Melnikov B., Melnikova A. 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. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–274.

Alekseeva A., Melnikov B. Iterations of finite and infinite languages and nondeterministic finite automata // Vector of Science of Togliatti State University. – 2011. – No. 3 (17). – P. 30–33 (in Russian).

Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part I //International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 4. – P. 1–11 (in Russian).

Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part II //International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 5. – P. 1–11 (in Russian).

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).

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an inverse morphism // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 5. – P. 1–8 (in Russian).

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part III. The condition for the existence of a lattice // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 7. – P. 1–9 (in Russian).

Melnikov B., Melnikova A. Some properties of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2002. – Vol. 9. No. 1. – P. 135–150.

Melnikov B., Sciarini-Guryanova N. Possible edges of a finite automaton defining a given regular language // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2002. – Vol. 9. No. 2. – P. 475–485.

Melnikov B., Sayfullina M. On some algorithms for equivalent transformation of nondeterministic finite automata // News of higher educational institutions. Mathematics. – 2009. – No. 4. – P. 67–72 (in Russian).

Melnikov B., Melnikova A. The use of petal finite automata to verify the fulfillment of a special case of the Zyu hypothesis (for a given finite language) // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 3. – P. 1–11 (in Russian).

Lallement G. Semigroups and Combinatorial Applications. – NY, John Wiley & Sons. – 1979. – 376 p.

Salomaa A. Jewels of Formal Language Theory. Computer Science Press, Rockville, Maryland (1981). – 144 p.

Skornyakov L. (Ed.) General Algebra. Vol. 1. – Moscow, Nauka. – 1990. – 592 p. (in Russian).

Hausdorff F. Grundzüge der Mengenlehre. – Grundzüge der Mengenlehre, von Veit. – 1914. – ISBN 978-0-8284-0061-9. (Reprinted by Chelsea Publishing Company in 1949.)

Gurov S. Boolean algebras, ordered sets, lattices: definitions, properties, examples. – Moscow, Librokom. – 2013. – 221 p. (in Russian).

Melnikov B., Melnikova A. A polynomial algorithm for constructing a finite automaton for checking the equality of infinite iterations of two finite languages // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 11. – P. 1–10 (in Russian).

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. Regular languages and nondeterministic finite automata (monograph). – Moscow, Russian Social State University Ed. – 2018. – 179 p. – ISBN 978-5-7139-1355-7 (in Russian).


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162