Prof. Boris Melnikov
Shenzhen MSU – BIT University, China
Title: Coverage relation for iterations of languages: algorithmic issues
Abstract:
We consider the following binary coverage relation for two finite languages: the first language is covered by the second one if and only if for any word from iteration of the first language there exists some word from iteration of the second one, such that the first of these words is a prefix of the second one. To verify the fulfillment of this relationship, we define a special deterministic finite automaton, depending on the both given languages. Considering such automata for all covered languages, we come to the conclusion that only a finite number of such covered languages can be considered, which gives a finite number of words possible for the possible covering language. For such a set of words, we define a special groupoid, on the basis of which all such deterministic finite automata for the language being covered can be described. We show that, generally speaking, the groupoid is not associative, and consider some examples of such groupoids.
Keywords Binary relation, iteration of language, deterministic finite automaton, non-associative groupoid
MR(2020) Subject Classification 20N02, 17D99, 20F10
Biography:
In 1979, I graduated from the Physics and Mathematics School at Moscow State University (currently Kolmogorov Mathematical School).From 1979 to 1984, I studied at Moscow State University (Faculty of Computational Mathematics and Cybernetics).Further, until 1992, I worked as a programmer at a scientific research institute, and since 1988, I simultaneously studied in correspondence postgraduate study at Moscow State University.In 1990, I defended my first dissertation (PhD), also at Moscow State University.Soon I began working at the Ulyanovsk Branch of Moscow State University, which was subsequently transformed into an independent university.At this university, I went through all the "steps" from assistant to professor, head of department; at the same time in 1997, I defended the "second Russian" dissertation (doctoral thesis, "Habilitation").
From 2003 to 2016, I worked at two other universities of Volga Region (Togliatti and Samara).In them, I was the Chairman of the Dissertation Council for 5 years, and the chief editor of a scientific electronic journal for 3 years.In 2016, I returned to Moscow, where I worked simultaneously in Moscow State University and Russian State Social University.In 1998-2014, I was 12 times the visiting professor at leading universities of Europe (including ETH-Zurich 3 times).In 1999-2019, I was scientific adviser of 13 candidates of sciences (PhD) already defended.I have about 40 presentations at international conferences outside Russia and about 100 international conferences in Russia.Since 2018, I have been working in China; I am Professor of Shenzhen MSU-BIT University.
Fields of my scientific interests: artificial intelligence and programming nondeterministic games; heuristic algorithms; discrete optimization problems; mathematical modeling; DNA sequence processing algorithms; nondeterministic finite automata and regular languages; non-traditional variants for setting context-free languages; semigroup algebra.