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

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 automataalgorithms 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 first part of this paper, we briefly describe all the necessary dichotomies, give the associated auxiliary designations, and also give new versions of the formulations of the two automata considered in previous papers.