Спросить
Войти
Some more on u-finite automata and u-regular languages. Part I: The main definitions and properties
B. F. Melnikov, A. A. Melnikova
Abstract—The finite and infinite iterations of finite and infinite languages arise in various problems of the formal languages theory. For instance, we can mention their application for the description of subclasses of the context-free languages class with the decidable equivalence problem. For infinite iterations of finite languages, we consider in this paper so-called strongly connected omega-automata and corresponding omega-regular languages. For them, many statements are fulfilled that are not satisfied in the more general case, i.e. when we use arbitrary omega-finite automata and corresponding omega-regular languages; the omega-iterations of languages include in the class of strongly connected omega-regular languages. The main of such properties and statements are non-existence of an omega-automaton for which there is no equivalent deterministic, and the possibility of checking the equivalence of two given omega-automata; in the general case (i.e., when we consider arbitrary omega-automata), both of these properties are not satisfied. We also describe transferring the usual procedure of determinization to the case of omega-automata and show the correctness of this procedure in the cases we are considering. We consider some examples, and in the second part of the paper, we shall consider the transfer of a well-known example (so called Waterloo automaton) to the case of omega-automata and omega-languages.
I. INTRODUCTION
The main subject of this paper is the connection between the known facts related to w-regular languages1 and iterations of languages (usually, infinite iterations of finite languages). However, we also consider some other statements related to w-languages, but not related to iterations of languages.
The iterations of finite and infinite languages arise in various problems of the formal languages theory. We cite only three relevant topics related to previous publications of the authors of this paper.
Received May 21, 2020.
Boris F. Melnikov, Shenzhen MSU-BIT University (email: bf-melnikov @yandex.ru).
Aleksandra A. Melnikova, Dimitrovgrad Engineering and Technology Institute - Branch of National Research Nuclear University "MEPhI" (email: super-avahi@yandex.ru).
However, the same spelling was also established in Russian mathematical literature, which carries some inaccuracy: "w" is related to the combination of words "regular languages" (or "finite automata"), not to the word "regular" (or "finite"), and therefore should be written with a dash (and not with a hyphen).
• The description of subclasses of the context-free languages class with the decidable equivalence problem. See [1] etc.
• The use of iterations of languages for describing the structure of the set of loops of the transition graph of a considered nondeterministic finite automaton and the equivalent basis automaton. See [2], [3], [4] etc.
• The connection between iterations of languages and some problems of the theory of approximation of semigroups. See [5], [6] etc.
Some clarification of the mentioned problems, as well as other links to our previous works are given below in preliminaries.
Thus, in connection with all of the above, we consider some facts related to w-finite automata2 and w-regular languages. We specifically note, that the terminology and basic concepts used by our paper are somewhat different from those used in [7].
We can say that the main objects considered in this paper are so-called strongly connected w-automata and corresponding w-regular languages. For them, many statements are fulfilled that are not satisfied in the more general case, i.e. when we consider arbitrary w-finite automata and corresponding w-regular languages. It is important to note that the w-iterations of languages (they are of particular interest to us) do include in this class. The main of these properties and statements are non-existence of an w-automaton for which there is no equivalent deterministic, and the possibility of checking the equivalence of two given w-automata. We note again that in the general case (i.e., when we consider arbitrary w-automata), both of these properties are not satisfied.
The structure of the paper is as follows. Sections II, III, and IV includes preliminaries:
• in Section II, we give notation related to the "usual" finite automata and regular languages3;
• in Section III, we consider notation related to arbitrary w-languages; we also consider there some facts on w-languages which is necessary for the remained part of the paper;
• and in Section IV, we consider w-automata: among various versions of w-automata, we shall consider so-called Buchi-automata only; moreover, we shall mainly use a special simplification of Buchi-automata, which is sufficient for the purposes of this paper.
In Section V, we consider a special subclass of the w-automata class. We called such objects iterating w-automata, and firstly introduce the definition and some examples for them. Corresponding w-languages are called iterating w-languages. And in Section VII, we introduce special subclasses of the classes of iterating w-automata and w-lan-guages: i.e. the classes of strongly connected w-automata and w-languages.
Before, in Section VI, we describe in details the transferring of the usual procedure of determinization (for usual finite automata) to the case of w-automata; we have to describe it, because we shall use the description in proving some further facts. For instance, in Section VII we prove a fact (Theorem 1), which shows the validity of this procedure for the class of w-finite automata.
We are going to continue the consideration of w-finite automata and corresponding w-regular languages in Part II of this paper. At the end of this part, we present the main results that we are going to publish in Part II.
II. Preliminaries: the main notation
For the usual finite automata and regular languages, we shall use notation of our previous papers. At first, see [8], [9]. Almost always, we considered nondeterministic finite automaton designated
K = ( Q, E,S, S,F). We specially note the following notation: the edge S(q, a) 3 q& (for finite automaton K) will be denoted
or q —> q&, or simply q —> q&
We also remark that we shall use designation Lin, which naturally generalizes to w-automata defined below. For instance, for automaton 1 and its state q G Q, Lin(q) is simply the language of the automaton
(Q, E, S, S, {q} ).
III. Preliminaries: w-languages
Among the monographs devoted to w-languages, we note [7] and the classical books [10], [11], [12]. A detailed theory of w-languages is also presented in the classical papers [13], [14], [15], [16]. Note once again, that the terminology and basic concepts used by our paper are somewhat different from those used in [7].
Words over a given alphabet are finite sequences of the letters, and an infinite a sequence of letters of a given alphabet is called an infinite word or w-word over this alphabet. The set (finite or infinite) of w-words is called an w-language.
The set of all w-words over the alphabet E is denoted by E". We shall denote
E~ = E* U E".
Below, the subsets of the set will be usually denoted by A and B.
(usually, the alphabet E is supposed to be finite. However, in some our papers it should be infinite, see at first [17]. See also [1], [18] etc. for some possible applications.)
For some given language L C E* ("usual" language), we shall define w-languages
lim(L) and adh(L).
Let us note in advance, that we can consider these w-languages as a connection between languages (subsets of the set E*) and w-languages (subsets of the set E").
Thus, let pref(u) (where u G E*) be the set of all the prefixes of u; similarly pref(a) (where a G ETO) be the (infinite) set of all the prefixes of a. For the languages (w-languages), we define
pref(A) = y pref(a).
Then for the given language L C E*, we set
lim(L) = { a G E" | (Vk G N) (3u G L) (|u| > k, u G pref(a)) }
adh(L) = { a G E" | (Vw G pref(a)) (3x G E*) (wx G L) }
It is east to prove, that
lim(L) C adh(L),
but, generally speaking,
lim(L) = adh(L) :
the simplest example for the last inequality is the language L, which can be defined by the regular expression a*b; for it, we have
lim(L) = 0 , but adh(L) = {a"} .
We also note the equality
adh(L) = lim (pref(L)),
which was proved in [12]; in the present paper; however, it does not play an important role for the further consideration.
We also note that for the infinite iterations of languages considered in some our works, the w-languages lim and adh are one and the same.4 This result can be considered as a consequence of the fact proved in [19, Th. 3.9].
Various methods are used to specify specific w-languages. Chronologically, the first to be applied the so-called L-systems, including their special cases: OL-systems, DTOL-systems, DOL-systems, etc. Apparently, these terms were introduced since 1968 only, see [20], [21], [22]. However, for example, the widely used in various areas of mathematics Thue-Morse w-word was actually described using DOL-systems much earlier, see [23], [24].
L-systems are described in detail in [12], some special cases of L-systems are defined in [25, Chap. 1,5]. Often, the infinite iterations of languages that we consider cannot be generally defined using DOL systems, and OL-systems are apparently not a very convenient object to use, so we shall only define DTOL systems that we shall use in the future. The definition is given according to [16].
A DTOL-system is a construction of the type
G = (E,hb...,h„,w), (2)
• E is the considered alphabet5;
• n > 1;
• each hi is a morphism of the type
Н, : E* ^ E*;
• w € E* is an "axiom"6.
By definition, the language of such DTOL-system (2) (i.e. DTOL-language L(G)) is the set of words
{ u € E* | (3«i, ...,ik € 1, n) (u = hik o- ■ -о Н,2 о hh (w)) }.
Let us remark, that for n = 1, this definition defines a DOL-system; see [25, Chap. 1]. The w-DTOL-language is by definition lim(L(G)).
In addition to various L-systems, w-languages can be determined using various versions of w-automata and w-grammars. These methods for defining w-languages have analogies with defining context-free languages by push-down automata and context-free grammars.
IV. Preliminaries: w-automata
Among various versions of w-automata, we shall consider so-called Buchi-automata only. (See [7] etc. For the primary source, see [26].) In fact, a Buchi-automaton can be defined in full accordance with the usual finite automaton: a tuple
K = ( Q, E,S,S,F). (3)
Formally, this coincides with (1); however, we have to make the following additions.
• Certainly, the set of final states F has a different meaning.
• In our previous papers, we considered the transition function S without e-edges, i.e. it is a function of the type
S : Q x E ^ P(Q). (4)
We make similar assumptions in this paper.
• In our previous papers, we sometimes considered w-automaton as a tetrad
K = ( Q, E,S,S), (5)
but not as the five like (3); see [27], [28] and sections later in this paper.7
• In addition, we have to define the w-language accepted by the automata (3) and (5), considered as w-automata.
However, we shall not consider a detailed definition, but consider its simplification. Thus, given the last things, we shall use the following modified definitions.8
Definition 1: An w-automaton is
K = ( Q, E,S,S,F), (6)
• Q is the set of states;
• E is the alphabet;
• S is the function of the type (4);
• S C Q is the set of initial states;
• F C Q is the set of special states, which could be called as final ones. □
Such automata are represented in the form of graphs in the usual way. Like our previous papers, we denote below all the states of usual automata (NFA) by double circles. (The single circles are used for so-called "proper" GNFPAs only, see [29] for details.) The initial and final states are marked by little input and output arrows respectively.
We specifically simplified two the following definitions a little: for our purposes, such a simplification is sufficient.
Definition 2: The w-word
a1a2... , where a e E for each i e N (7)
is an w-sequence of w-automaton (6), if there exists an infinite sequence of states
q0 , q1, q2, ... , where q e Q for each i e No , (8)
for which the following conditions hold:
• qo e S;
• (Vi G N)(S(qi_i,ai) 3 qi). □
Definition 3: The w-word
a1a2... , where a4 e E for each i e N
is accepted by w-automaton (6), if it is the w-sequence of this w-automaton, and in addition, the following conditions hold:
• there exists f e F, such that the sequence (8) contains f infinitely many times.10
The w-language accepting by w-automaton (6) (or simply "w-language of w-automaton") is the set of w-words accepting by it. □
Of course, for such definitions we are interested in the usual problems of language theory. First, how to determine the equivalence of two w-automata (that is, do the given w-automata define the same w-language)? Secondly, does there exist a deterministic w-automaton equivalent to a given one?11 Therefore, we must first determine the deterministic w-automaton, which is done in the usual way.12
Definition 4: The w-automaton of Definition 1 is deterministic, if the following conditions hold13:
• |S |< 1;
• (Vq e Q , a e E)(|S(q,a)| < 1). □
A well-known example answers the second question negatively. Namely, let us consider the following automaton (Fig. 1):
It is evident, that the w-language of this w-automaton could be determined by the expression14
(a + Ъ)* • Ъш.
The usual procedure of making the deterministic automaton15 gives the following w-automaton (Fig. 2):
(where A corresponds to the set {1}, and B corresponds to the set {1,2}). Certainly, it is not equivalent to the w-automaton of Fig. 1: for instance, the w-language of the last w-automaton contains w-word
(ab)",
which is not included in the w-language of the first w-automaton.16
Thus, we answered negatively to the second of the questions asked above; that is, not for any w-automaton there exists an equivalent deterministic one. Further we shall consider particular cases in which a different situation is observed.
All this allows us to consider the following definition, or rather, makes it meaningful.
Definition 5: The class of deterministic w-languages
includes only those w-languages, each of which can be accepted by an deterministic w-automaton. □
In the conclusion of the section, we note once again that the designation Lin that we shall use in the future is not necessary to redefine for w-automata.
V. ITERATING w-AUTOMATA: THE DEFINITION
In this section, we shall consider a special subclass of the w-automata class.
As we have already noted, in many of our previous works, we considered problems related to iteration of languages, as well as to binary relations related to such iterations of (usually finite) languages. See the papers [1], [5], [6], [17], [18], [19] cited before, and also [31], [32] etc.
A generalization of such iterations to case of w-languages are w-iterations. Above, we defined them using L-systems; now, we shall consider a simpler definition of them. For the following, the iterating set does not contain the empty word (i.e. A ft e when we use notation A"); this limitation is because otherwise, the following definition accepts not only w-words, but also usual words. Like alphabet E, the set A is usually finite; however, as we noted before, in [17] we considered cases, when either E or A should be infinite; we also already cited [1], [18] for some possible applications.
Definition 6: An iterating w-language (of the language
A" = ^Q uj, where uj G A for each i g N.
(Here, we used the natural generalization of the concatenation operation, when its right operand is an w-word.) □
We also note that according to, for example, already cited papers [13], [14], [22], we can assume that the infinite iterations of languages discussed below are special subsets of the so-called w-deterministic context-free languages class (this is a more general object than the w-languages of the deterministic w-finite automata). However, in our case (i.e. for iterating w-languages) we can consider exactly the (nondeterministic) w-finite automaton defined by the next Definition 7. We note in advance that we strictly define an object schematically depicted on the following Fig. 3.
For Definition 7, we shall use notation
A = { ui, u2,..., u„ } .
Let us especially note, that the use of ui differs from that used in the previous Definition 6.
Definition 7: Let
Ui — ai,iai,2 . .. ai,i17
where a^j G E, Zi G N for i G 1, n.
Then an iterating w-automaton (of the language A) is
( Q, E , S, {qo} , {qo} ) ,
Q = {qo} U (^J qi,j,
jei,¡¡-T
and the transition function S is defined in the following way.
• For each i e 1, n:
- S(qo,aiji) = {qi,i};
- for each j e 1, k - 2, S(q*,j, aj,j+i) = {qij+i};
- S(qi,;i_i,ai,;i) = {qo}.
• For all remaining pairs q e Q and a e E, we set
S(q, a) = 0 . □
In any infinite path of the transition graph of the w-automaton of Definition 7, the state qo occurs infinite number of times. Therefore Definitions 6 and 7 do define the same w-language.
VI. The formal definition of determinization
PROCEDURE IN CASE OF w-AUTOMATA
In this section, we consider the usual procedure of deter-minization; more precisely, we consider its transferring to the case of w-automata. This procedure is valid standard; however, it must be considered in detail for the following three reasons:
• firstly, for usual automata, the different formulations of the corresponding algorithm are given in different monographs (and especially the specific description of such algorithms);
• secondly, we have to describe it, because we shall use the description in proving some facts;
• thirdly, we have to describe it, because not quite standard is working with the set F: in the usual case, they are used to describe the sets of useless and not-useless states, and in our case, as can be seen from the above examples, it is hardly possible to draw a corresponding analogy.18
We note once again that, according to the material of Section IV, that we do not guarantee equivalence of the both w-automata: the given one and the one obtained after the transformation.19
Below, P(A) denotes the superset for the given set A.20 Similar (but not the same) notation will be used for the automata. Thus.
Definition 8: Let the w-automaton K (6) be given. w-automaton P(K) is defined in the following way.
P(K) = ( Q, E,Sq, {S}, F),
• Q = P (Q);
• Se is defined as follows: the edge
q —^ q&, where q, q& eP (Q), a e E
exists if and only if
(3q e q, 3q& e q&) (q q&);
• F = {f eP (Q)|(3f e F) (f e f) }. □
The following fact is very easily proved21: if K and P(K) are considered as the usual automata, then they are equivalent. However we note once again, that, generally speaking, w-automata K and P(K) are not equivalent.
Authors hope that the examples of Section IV should not cause any questions; moreover, they can be considered as the examples to the definition given in this section.
VII. STRONGLY CONNECTED w-AUTOMATA: THE DEFINITION AND THE MAIN PROPERTY
Let us note at first, that the notation of the graph theory is consistent with the classical book [30].
The following definition is very natural. It introduces special subclasses of the classes of w-automata and w-languages considered in the previous section.
Definition 9: An w-automaton is called strongly connected one, if its transition graph is strongly connected. □
Certainly, automaton on Fig. 1 is not strongly connected.
Obviously, the definitions for both pairs of classes we introduced (i.e. iterating / strongly connected w-languages/ w-automata) can be reformulated for "usual" regular languages and nondeterministic finite automata. In this case, the definitions for the corresponding "usual" languages are naturally introduced. Moreover, it can be proved that such definitions are meaningful, i.e. they introduce the own subclasses of the regular languages class.22 We are going to return to this issue in a future publication.
The following theorem seems to be simple, but the authors did not find it in the available literature.
Theorem 1: Let the strongly connected w-automaton K (6) be given. Then the w-automata K and P(K) are equivalent.
Proof. We have to prove the following 4 parts:
K ^ P(K) (1) (3)
P(K) ^ K (2) (4)
Thus, let us prove these facts.
For this thing, there is enough prove by induction, that for the given w-word (7) and for each n g N0, the following holds: ( )
(3q G Q) (Lpn(K) (q) 3 aia2 ...a„). (10)
Besides, we can assume the existence of the set of states (8) of the automaton K.
For the base of induction, we choose q0 = {S}. Let us prove the step. We assume (10). By Definition 2, we have
qn —qn+i. (11)
By Definition 8, we select q& : namely, we select it using the edge (11). Then we obtain (10) for n +1 instead of n and q& instead of q, and we can say, that we built the necessary sequence of states for the automaton P(K), Q.E.D.
Let us reformulate a part of Definition 8 for w-automaton P(K). We have, that for the given w-word (7), there exists an infinite sequence of states
q0 , qi, q2, ... , where qi G Q for each i G N0 , (12)
for which the following conditions hold:
• q0 = {S};
• (Vi G N)(S(qj_i,ai) = {qj)}
(we also changed both "g" and "3" for the equality because of the determinism).
Then there is enough prove by induction, that:
• for the given w-word (7);
• for the corresponding sequence of states
q0 , qi, q2, ... (qi G Q for each i g N0), (13)
(we obtained it changing the sequence (8); we can see, that it coincides with the sequence (12) used when proving the direct inclusion);
• and for each n g N0, the following condition holds:
(3q G Q) (Lc (q) 3 aia2 ...an). (14)
By Definition 2 for automaton P(K), we have its edge
S(qi, aj+i) = {qi+i}
for the letter ai+i of the given w-word (7).
By Definition 8 for automaton P(K), we obtain existing an edge of the type (11), where
(it is a consequence of the induction hypothesis), and also
qn+i G qn+i. The last fact proves the induction step, Q.E.D.
Let us consider some w-word of w-automaton K. By Definition 3, the corresponding sequence of states (8) has the following property: for some f G F, this sequence includes a subsequence (let it be the sequence a), which includes f infinitely many times. For each such inclusion, we have a corresponding state of the sequence (13); and because this
state (considered as a set of states of Q) includes f, it belongs to F. Thus, each state of a corresponds to a state of F; then, because a is infinite, there exists a state of F which enters a an infinite number of times. Then, by Definition 8, the considered w-word belongs to w-language of the automaton K. Q.E.D.
Let us consider some w-word of w-automaton K. By Definitions 3 and 8, the corresponding infinite sequence of states (13) contains infinitely many states f gP (Q), such that f э f for some f g F. If for each f g F, the corresponding sequence of the states of K contains the finite number of f only, then for none f g F, we could not form the infinite number of f in the sequence (13), and this contradicts the possibility of accepting the considered w-word by the given w-automaton K. Q.E.D. □
To conclude this section, let us give the following natural definition.
Definition 10: The w-language is called strongly connected if it can be accepted by an strongly connected w-automaton. □
As we saw from the previous exposition, this definition is meaningful, i.e. the subclass of strongly connected w-languages is the own subclass of the w-languages class. However, we have not yet answered the question whether this subclass includes any deterministic w-regular language.
On Part II of this paper
In Part II of this paper, we shall continue the consideration of the subclasses of w-regular languages and w-finite automata classes we have defined in Part I. For instance, we shall consider an effective algorithm for determining the fact that some w-language is the iterating one. We also shall consider the transfer of a well-known example (so called Waterloo automaton) to the case of w-automata and w-languages.
References
[1] Melnikov B., KashlakovaE. Some grammatical structures of programming languages as simple bracketed languages // Informatica (Lithuanian Academy of Sciences). - 2000. - Vol. 11. No. 4. - P. 441-454.
[2] Melnikov B., MelnikovaA. Edge-minimization of non-deterministic finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). - 2001.
- Vol. 8. No. 3. - P. 469-479.
[3] Melnikov B., MelnikovaA. Extended basis finite automaton. Part I. The basic definitions // International Journal of Open Information Technologies. - 2019. - Vol. 7. No. 10. - P. 1-8. (in Russian)
[4] Melnikov B., MelnikovaA. Extended basis finite automaton. Part II. Description of auxiliary languages and some properties // International Journal of Open Information Technologies. - 2020. - Vol. 8. No. 5. -P. 1-7. (in Russian)
[5] Dang V., Korabel&shchikova S., Melnikov B. Semigroups approximation with respect to some ad hoc predicates // Arctic Environmental Research. - 2017. - Vol. 17. No. 2. - P. 133-140.
[6] Melnikov B., Korabelshchikova S., Dolgov V. On the task of extracting the root from the language // International Journal of Open Information Technologies. - 2019. - Vol. 7. No. 3. - P. 1-6.
[7] Khoussainov B., Nerode A. Automata Theory and its Applications // Progress in Computer Science and Applied Logic, Vol.21. - Springer, Berlin, 2001.
[8] Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae.
- 2010. - Vol. 104. No. 3. - P. 267-283.
[9] Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. - 2017. - Vol.5. No. 10. - P. 9-17.
[10] Eilenberg S. Automata, Languages and Machines. Vol. A // Academic Press, N.Y., 1974.
[11] Eilenberg S. Automata, Languages and Machines. Vol. B // Academic Press, N.Y., 1976.
[12] Rozenberg G., Salomaa A. The Mathematical Theory of L Systems // Academic Press, N.Y., 1980.
[13] Cohen R., Gold Y. Theory of w-Languages. I: Characterizations of w-Context-Free Languages // Journal of Computer and System Sciences.
- 1977. - Vol. 15. - P. 169-184.
[14] Cohen R., Gold Y. Theory of w-Languages. II: A Study of Various Models of w-Type Generation and Recognitions // Journal of Computer and System Sciences. - 1977. - Vol. 15. - P. 185-208.
[15] Culik II K., Pachl J. Equivalence Problems for Mapping on Infinite Strings // Information and Control. - 1981. - Vol.49. - P. 52-63.
[16] (Culik II K., Salomaa A. Test Sets and Cheking Words for Homomor-phism Equivalence // Journal of Computer and System Sciences. - 1980.
- Vol. 20. - P. 379-395.
[17] Brosalina A., Melnikov B. Commutation in global supermonoid of free monoids // Informatica (Lithuanian Academy of Sciences). - 2000. -Vol.11. No. 4. - P. 353-370.
[18] DubasovaA., Melnikov B. On an extension of the context-free languages class // Programming and Computer Software (Russian Academy of Sciences). - 1995. - No. 6. - P. 46-55. (in Russian)
[19] Melnikov B. An algorithm for checking the equality of infinite iterations of finite languages // Bulletin of Moscow University, series Computational Mathematics and Cybernetics. - 1996. - No. 4. - P. 4954. (in Russian)
[20] Lindenmayer A. Mathematical models for cellular interaction in development. I // Journal of Theoretical Biology. - 1968. - Vol. 18. -P. 280-298.
[21] Lindenmayer A. Mathematical models for cellular interaction in development. II // Journal of Theoretical Biology. - 1968. - Vol. 18. -P. 299-315.
[22] Wood D. Grammar and L Forms: an Introductions // Springer, Berlin, 1980.
[23] Thue A. Über unendlichen Zeichenreihen // Math.-Naturv. Klasse Skrifter udgivne af Videnskabsselskabet i Christiania. - 1906. - P. 1-22. (in German)
[24] Thue A. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen // Math.-Naturv. Klasse Skrifter udgivne af Videnskabsselskabet i Christiania. - 1912. - P. 1-35. (in German)
[25] Salomaa A. Jewels of Formal Language Theory // Computer Science Press, Rockville, 1981.
[26] Btichi 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.25
- P. 425-435.
[27] Melnikov B. On w-languages of special billiards // Discrete Mathematics (Russian Academy of Sciences). - 2002. - No. 3. - P. 95-108. (in Russian)
[28] Melnikov B. On w-languages of special billiards // Discrete Mathematics and Applications. 2002. - Vol. 12. No. 5. - P. 501-514.
[29] Melnikov B., Melnikova A. Pseudo-automata for generalized regular expressions // International Journal of Open Information Technologies. 2018. - Vol.6. No. 1. - P. 1-8.
[30] Harary F. Graph Theory // Addison-Wesley, Reading, 1969.
[31] Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Sciences. 1993. - Vol.4. No.3. - P. 267-274.
[32] Melnikov B. The star-height of a finite automaton and some related questions // International Journal of Open Information Technologies. 2018. - Vol.6. No.7. - P. 1-5.
Boris Feliksovich MELNIKOV,
Professor of Shenzhen MSU-BIT University, China
(http://szmsubit.ru/),
Professor of Russian State Social University
(http://www.rgsu.net/), email: bf-melnikov@yandex.ru, mathnet.ru: personid=27967, elibrary.ru: authorid=15715, scopus.com: authorId=55954 04 030 0, ORCID: orcidID=00 0 0-0 0 02-67 65-68 0 0.
Aleksandra Aleksandrovna MELNIKOVA, Associated Professor of
Dimitrovgrad Engineering and Technology Institute -Branch of National Research Nuclear University "MEPhI"
(https://diti-mephi.ru/), email: super-avahi@yandex.ru, mathnet.ru: personid=148963, elibrary.ru: authorid=143351, ORCID: orcidID=00 0 0-0 0 02-165 8-6857.
