A polynomial algorithm for checking the fulfillment of the condition of the morphic image of the extended maximal prefix code
Abstract
The maximum prefix code is defined in the usual way, “based on the things stated in the student courses”. An extended maximum prefix code is a finite language containing some maximum prefix code as a subset (proper or improper one). Also the (homo)morphism is defined in the usual way, and, based on it, the inverse morphism does. In our previous publications, infinite iterations of finite languages as om−languages have been considered. A hypothesis was formulated that infinite iterations of two given finite languages coincide if and only if both of these languages can be obtained using the following algorithm. First, some new alphabet is selected; secondly, some two extended maximal prefix codes are considered over this alphabet; third, to these two extended maximal prefix codes, some morphism is applied (the same in both cases), which translates words over the new alphabet into words over the original alphabet. At the same time, the obtained morphic images of the two considered extended maximal prefix codes should coincide with the two given finite languages. (More precisely, some equivalent versions of this hypothesis have been formulated, as well as another hypothesis, which has a less strong statement, but which makes sense to talk about if the first hypothesis is not fulfilled.) This paper solves the problem of checking whether one language can be obtained using a similar algorithm applied to some other language. More precisely, a non-deterministic algorithm for such a problem is trivial, and was given in one of our previous publications; here we also give a deterministic polynomial algorithm for checking the fulfillment of this condition. Thus, the problem considered in this paper can be considered a step towards verifying the formulated hypothesis.
Full Text:
PDF (Russian)References
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 Variants of finite automata corresponding to infinite
iterative morphism trees. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 7. – P. 5–13 (in
Russian).
Melnikov B Variants of finite automata corresponding to infinite
iterative morphism trees. Part II // International Journal of Open
Information Technologies. – 2021. – Vol. 9. No. 10. – P. 1–8 (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.
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).
Мельников Б. Подклассы класса контекстно-свободных языков
(монография). – М., Изд-во Московского университета. – 1995. –
с. – ISBN 5-211-03448-1.
Abramyan M., Melnikov B. Algorithms of transformation of
finite automata, corresponding to infinite iterative trees // Modern
information technologies and IT education. – 2021. – Vol. 17. No. 1.
– P. 13–23. (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).
Lallement G. Semigroups and Combinatorial Applications. – NJ,
Wiley & Sons, Inc. – 1979. – 376 p.
Graham R., Knuth D., Patashnik O. Concrete Mathematics.
A foundation for computer science. – USA, Addison-Wesley
Professional. – 1994. – xiv+657 p.
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162