Eight variants of finite automata for checking the fulfillment of the coverage relation of iterations of two finite languages. Part II

Boris Melnikov, Lingqian Meng

Abstract


The task for which all automata of this paper are considered is to describe algorithms for checking the so-called binary coverage relation, which was considered in many of our previous papers: it is performed for two nonempty finite languages if and only if any iteration of words of the first language is a prefix of some iteration of words of the second language. This task can be viewed from several different points of view, which was done in previous works.
In this paper, we are primarily interested in various variants for implementing algorithms to verify the fulfillment of this relationship, and more specifically, the use of finite automata for such algorithms. 2 variants of such automata have already been previously described in our previous works, and in this paper we add 6 more variants to them. The main purpose of considering several automata algorithms is as follows. Earlier, we described a polynomial algorithm for constructing one of these automata. However, the existence of such a polynomial algorithm does not mean that we can check the fulfillment of the condition we need in a polynomial way, due to the following circumstance. If we build a nondeterministic automaton to answer the question in the same way as we described earlier, then for a positive answer. it must accept any word of the universal language; the last condition cannot be checked in polynomial time. However, we also cannot say that such a polynomial algorithm does not exist:  additional research is needed. Therefore, the presence of four descriptions of nondeterministic automata that answer the question about the fulfillment of the considered binary relation will give some new opportunities to search for a possible algorithm that checks the main condition of the paper in polynomial  time. 8 variants of the automata considered in the paper are naturally obtained  using three different dichotomies: one of them is the “usual” one (whether the  automaton is deterministic), and the other two dichotomies are directly related to the issues of checking the implementation of the binary coverage relation considered in the paper. Specifically, these two dichotomies are as follows: first, which of the two finite languages under consideration is the “main” one (it is that for which we apply the basic morphism to check); secondly, do we consider the required covers of each iteration word directly when it occurs, or not immediately, but after the formation of some auxiliary language. In the presented second part of the paper, we continue to describe variants of finite automata for checking the fulfillment of the coverage relation.


Full Text:

PDF (Russian)

References


Melnikov B.F., Meng Lingqian. Eight variants of finite automata for checking the fulfillment of the coverage relation of iterations of two finite languages. Part I. // International Journal of Open Information Technologies. 2023. Vol. 11, No. 11. P. 1–9. (in Russian)

Khoussainov B., Nerode A. Automata Theory and its Applications // Progress in Computer Science and Applied Logic, Vol. 21. – Springer, Berlin, 2001.

Büchi J. On a decision method in restricted second order arithmetic // In: Proceedings of International Congress on Logic, Method, and Philosophy of Science. – Stanford University Press, Stanford, 1962. – P. 425–435.

Melnikov B.F. On ω-languages of special billiards // Discrete Mathematics (Russian Academy of Sciences). – 2002. – No. 3. – P. 95–108. (in Russian)

Melnikov B.F., Vakhitova A.A. Some more on the finite automata // Journal of Applied Mathematics and Computing. 1998. – No. 3. – P. 495–505.

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

Melnikov B.F., Melnikova A.A. Some more on ω-finite automata and ω-regular languages. Part I: The main definitions and properties // International Journal of Open Information Technologies. 2020. Vol. 8, No. 8. P. 1–7.

Melnikov B.F. Algorithm for checking the equality of infinite iterations of finite languages // Bulletin of the Moscow University. Series 15: Computational Mathematics and Cybernetics. 1996. – No. 4. – P. 49–55. (in Russian)

Melnikov B.F. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. 2010. – Vol. 104. No. 3. – P. 267–283.

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

Melnikov B.F. 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)


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162