### A polynomial algorithm for constructing a finite automaton for determining the equality of infinite iterations of two finite languages

#### Abstract

#### 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. ??. – P. ??–?? (in Russian).

Kameda T., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. – 1970. – Vol. C19. No. 7. – P. 617–627.

Polák L. Minimizations of NFA using the universal automaton // International Journal of Foundation of Computer Sciences. – 2005. – Vol. 16. No. 5. – P. 999–1010.

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., Tsyganov A. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method // In: Proceedings – 5th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP–2012. – 2012. – P. 194–201.

Dolgov V., Melnikov B. Building a universal finite automaton. I. From the theory to the practical algorithms // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2013. – No. 2. – P. 173–181 (in Russian).

Dolgov V., Melnikov B. Building a universal finite automaton. II. Examples of how algorithms work // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2014. – No. 1. – P. 78–85 (in Russian).

Abramyan M., Melnikov B. An approach to algorithmizing the problem of vertex minimization of nondeterministic automata. Part I. Problem statement and the brief description of the basis methods // In: IOP Conference Series: Materials Science and Engineering. Krasnoyarsk Science and Technology City Hall of the Russian Union of Scientific and Engineering Associations. – 2020. – C. 52055.

Markov A. Theory of algorithms (Proceedings of the V. Steklov Mathematical Institute. Vol. 42). – Moscow, Leningrad: USSR Academy of Sciences Ed. – 1954. – 376 p. (in Russian).

Igoshin V. Mathematical logic and theory of algorithms. – Moscow: Akademia. – 2004. – 447 p. (in Russian).

Skornyakov L. (Ed.) General Algebra. Vol. 2. – Moscow, Nauka. – 1991. – 480 p. (in Russian).

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

Pin J.E. Mathematical Foundations of Automata Theory. – Berlin, SpringerVerlag. – 2012. – 310 p

### Refbacks

- There are currently no refbacks.

Abava Кибербезопасность FRUCT 2023

ISSN: 2307-8162