نبذة مختصرة : 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 ...
Processing Request
No Comments.