A polynomial algorithm for checking the fulfillment of the condition of the morphic image of the extended maximal prefix code

Boris Melnikov, Aleksandra Melnikova

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  Кибербезопасность FRUCT 2024

ISSN: 2307-8162