Nondeterministic finite automata (NFA) and regular languages —
alternative descriptions of the invariants of regular languages,
state-marking functions,
sufficient conditions for unambiguity,
algorithms of equivalent transformation,
solution of the star-height problem
by describing the set of cycles of the basis automaton,
alternative methods of constructing Conways universal automaton,
exact algorithms of NFA-minimization by various criteria
(state-, edge- and star-height-minimization),
various formalisms-generalizations of NFA,
investigation of generalized regular expressions
and generalized star-height problem.
Context-free languages —
non-traditional variants for setting CF-languages
(using some generalizations of finite automata),
sequential CF-languages and their using for setting some programming languages,
subclasses of CF-languages class with a decidable equivalence problem.
Semigroup algebra —
commutativity condition in supermonoid of the free monoid,
binary relations on the elements of supermonoid,
descriptions of special submonoids of supermonoid,
infinite calculations of finite automata (also $2\omega$-calculations)
and their relationship with submonoids of supermonoid,
billiard languages (and $\omega$-languages) and monomial algebras,
billiard languages and public-key cryptography,
algorithmic questions of semigroup algebra
and computational methods for constructing descriptions
of submonoids of supermonoid
and corresponding binary relations.
Discrete optimization problems —
the use of anytime algorithms in various areas, such as:
classical puzzles, DNF-minimization,
NFA-minimization by various criteria (state, edge and star-height criteria),
pseudo-geometrical version of the traveling salesman problem,
binary phase-manipulation radio signals correlation noise minimizing.
Heuristic algorithms —
quick algorithms for decision making in the case of multi-criteria optimization,
various modifications of the branch-and-bound method,
multiheuristical approach,
genetic algorithms and tournament approaches to the self-learning,
simulation annealing and hybrid algorithms.
Describing the approach to estimating the representativeness
of randomly generated input.
Describing the approach to (heuristic) estimations
of the effectiveness of heuristic algorithms.
Distributed computing for solving discrete optimization problems.
Generalizations of the concepts of approximation and approximation algorithms.
Programming of nondeterministic games and artificial intelligence —
description of the modifications of the search-tree for various nondeterministic games,
the use of risk functions to select the move,
tournament self-learning GA,
imitation of opponent thinking in various problems of AI,
the use of analogs of production rules in intelligent game programming,
the use of "game" heuristics in discrete optimization problems.
Biography
(Full) professor, 2002.
Doctor of Mathematical and Physical Sciences, 1997;
defence: Lomonosov Moscow State Univ.,
Faculty of Computational Mathematics and Cybernetics;
thesis: "Applying the properties of special monoids
in the theory of formal languages".
Candidate of mathematical sciences, 1990; defence: Lomonosov Moscow State Univ.,
Faculty of Computational Mathematics and Cybernetics;
thesis: "A method of research of infinite iterations of languages".
Supervisor: L.Stanevičiené.
Graduation work, 1984;
defence: Lomonosov Moscow State Univ.,
Faculty of Computational Mathematics and Cybernetics;
thesis: "Algebra of programming graphs".
Supervisor: R.Smelyanskiy.
Graduated from Kolmogorov Mathematical School of Moscow State Univ., 1979.
Professional appointments:
July 2013 to date: Samara State University.
2003-2013: Professor of Department of Applied Mathematics,
Faculty of Mathematics and Informatics,
Togliatti State University (Russia).
(at the same time, 2008 to date:
Head of the Council for defenses of Doctors degrees,
Togliatti State University (Russia)).
2001 to 2003:
Professor of Department of Foundation of Computer Sciences,
Faculty of Information Technologies,
Ulyanovsk State University (Russia).
1999 to 2001: Professor of Department of Applied Mathematics,
Faculty of Mathematics and Mechanics,
Ulyanovsk State University (Russia).
1995 to 1999: Associated Professor of Department
of Mathematics and Cybernetics,
Faculty of Mathematics and Mechanics,
Ulyanovsk State University (Russia).
1991 to 1995: Senior Lecturer of Department
of Mathematics and Cybernetics,
Faculty of Mathematics and Mechanics,
Ulyanovsk Branch of Moscow State Lomonosov Univ.
1984 to 1991: Programmer, senior programmer
in Nuclear Research Institute (ex-Leningrad, ex-USSR).
1988 to 1990: Correspondence post-graduate student
of Faculty of Computational Mathematics and Cybernetics,
Moscow State Lomonosov Univ.
1979 to 1984: Student of Faculty
of Computational Mathematics and Cybernetics,
Moscow State Lomonosov Univ.
International activity (Visiting professor etc., 1-3 months.):
1998 – Germany, Leipzig & Dieburg, Fachhochschule Telekom;
2000 and 2001 – Bulgaria, Varna, Tekhnicheski Universitet;
2004 – Czech Republic, Brno, Masarykova Univerzita;
2006 and 2008 – Switzerland, Zürich, Eidgenössische Technische Hochschule;
2009 – Italy, Politecnico di Milano;
2010 – Slovakia, Bratislava, Univerzita Komenského;
2011 – Germany, Berlin, Humbolt Universität.
Research activity:
2008 to date: Head of the Council for defenses of Doctors degrees,
Togliatti State University (Russia),
http://edu.tltsu.ru/sites/site.php?s=1496&m=14453, in Russian).
2008 to date: Member of the Council for defenses of Doctors degrees,
Kazan (Volga Region) Federal University (Russia).
2000 to 2008: Member of the Council for defenses of Doctors degrees,
Ulyanovsk State University (Russia).
Director of Ph.D. theses already defended:
1. Alexey Radionov, 1999.
2. Elena Tarasova, 2006.
3. Elena Melnikova, 2009.
4. Maria Zuzanova, 2010.
5. Alexander Panin, 2011.
6. Svetlana Baumgaertner, 2012.
7. Stanislav Eirich, 2012.
8. Tatyana Zubova, 2012.
9. Olga Rogova, 2012.
10. Anna Alekseeva, 2012.
(The titles of their theses are given on the Russian version of this web-page.)
Director of 3 master theses already defended.
Director of 61 graduation (5-years bachelor) theses already defended.
Grants for scientific research
(of Russian Foundation for Basic Research, RFBR):
1999 to 2013: three 3-years Basic Grants;
2001: Grant of RFBR for the popular scientific papers;
2005 to 2012: four Grants for scientific conferences outside Russia;
2007: Grant for translating scientific books.
2000 to 2002: Grant of the President of Russia
("Professors before 40 years");
Other Russian grants for scientific research:
1993 to 1995: two Grants of the scientific program "Universities of Russia";
1996 to 1997: Grant of the Ministry of Education of Russia
for the scientific researches in Germany;
2007 to 2012: four Grants of the Ministry of Education of Russia
for the scientific researches in Togliatti State Univ.
European grants for scientific research:
2009: Grant of Landau Network-Centro Volta and Cariplo Foundation
for scientific researches in Italy;
2011: Grant of German Academic Exchange Service (DAAD)
for scientific researches in Germany.
B.F. Melnikov, “On the non-existence of a simple version of the polynomial algorithm for extracting the root from the language”, Vestn. YuUrGU. Ser. Vych. Matem. Inform., 13:1 (2024), 38–56
2023
2.
B.F. Melnikov, “On a hypothesis of the theory of formal languages. Part I”, Vestn. YuUrGU. Ser. Vych. Matem. Inform., 12:3 (2023), 72–86
2022
3.
B. Melnikov, Yu. Yu. Terent'eva, “On a graph model for reflectometry issues and some algorithms for their solution. Part 1. Issue statement and approaches to algorithmics”, University proceedings. Volga region. Physical and mathematical sciences, 2022, no. 2, 28–39
4.
B. Melnikov, Yu. Yu. Terent'eva, “On a graph model for reflectometry issues and some algorithms for their solution. Part 2. An approach to software implementation”, University proceedings. Volga region. Physical and mathematical sciences, 2022, no. 3, 32–42
5.
B. Melnikov, Yu. Yu. Terent'eva, “On a graph model for reflectometry problems and some algorithms for their solution. Part 3. An approach to test data generation and some results of computational experiments”, University proceedings. Volga region. Physical and mathematical sciences, 2022, no. 4, 31–41
2019
6.
V. V. Dang, N. Dodonova, S. Yu. Korabel'shchikova, B. Melnikov, “SH-weak duality of semigroups and minimum semi-group of SH-approximation”, University proceedings. Volga region. Physical and mathematical sciences, 2019, no. 1, 29–39
7.
V. V. Dang, S. Yu. Korabel'shchikova, B. Melnikov, “Approximated class”, University proceedings. Volga region. Physical and mathematical sciences, 2019, no. 4, 51–59
2018
8.
B. Melnikov, E. V. Davydova, A. V. Nichiporchuk, M. A. Trenina, “Clustering of situations in the algorithms for solving the traveling salesman problem and its application in some applied tasks. Part II. List metrics and some related optimization problems”, University proceedings. Volga region. Physical and mathematical sciences, 2018, no. 4, 62–77
9.
B. Melnikov, E. A. Mel'nikova, S. Pivneva, E. V. Davydova, “Clustering of situations in solution algorithms of the traveling salesman problem and its application i some applied problems. Part I. General description of problems and algorithms”, University proceedings. Volga region. Physical and mathematical sciences, 2018, no. 3, 36–51
10.
B. Melnikov, M. A. Trenina, A. S. Kochergin, “An approach to improving algorithms for computing distances between DNA chains (by the example of the Needleman - Wunsch algorithm)”, University proceedings. Volga region. Physical and mathematical sciences, 2018, no. 1, 46–59
2017
11.
V. V. Dang, S. Yu. Korabel'shchikova, B. Melnikov, “Some issues of semigroups approximation”, University proceedings. Volga region. Physical and mathematical sciences, 2017, no. 4, 46–57
12.
B. Melnikov, S. Yu. Korabel'shchikova, N. P. Churikova, “On verification algorithms for some binary relations on the general supermonoid of a free monoid”, University proceedings. Volga region. Physical and mathematical sciences, 2017, no. 3, 87–99
2015
13.
B. Melnikov, S. Pivneva, M. A. Trifonov, “Estimation of algorithms for calculation of distance between DNA lines”, University proceedings. Volga region. Physical and mathematical sciences, 2015, no. 2, 57–67
14.
S. B. Makarkin, B. Melnikov, M. A. Trenina, “Approach to solve a pseudogeometric version of the traveling salesman problem”, University proceedings. Volga region. Physical and mathematical sciences, 2015, no. 2, 135–147
15.
V. V. Dang, S. Yu. Korabel'shchikova, B. Melnikov, “On the problem of finding minimum semigroup of approximation”, University proceedings. Volga region. Physical and mathematical sciences, 2015, no. 3, 88–99
2014
16.
A. R. Belozerova, B. Melnikov, “Approach to mathematical simulation of transmutational processes in nuclear power plants”, University proceedings. Volga region. Physical and mathematical sciences, 2014, no. 2, 88–100
17.
B. Melnikov, E. A. Mel'nikova, A. N. Radionov, “Approach to nondeterministic games programming (Part II: Special heuristics and examples)”, University proceedings. Volga region. Physical and mathematical sciences, 2014, no. 2, 49–58
2013
18.
B. Melnikov, E. A. Mel'nikova, “Approach to programming of nondeterministic games (Part I: Description of general heuristics)”, University proceedings. Volga region. Physical and mathematical sciences, 2013, no. 4, 29–38
19.
B. Melnikov, E. F. Sayfullina, “Applying multiheuristic approach o randomly generating graphs with a given degree sequence”, University proceedings. Volga region. Physical and mathematical sciences, 2013, no. 3, 70–83
20.
S. V. Baumgertner, B. Melnikov, “Generalized indeterministic finite automata”, University proceedings. Volga region. Physical and mathematical sciences, 2013, no. 2, 64–74
2012
21.
B. Melnikov, A. A. Melnikova, “Multidimensional minimization of nondeterministic finite automata (Part II. Basic algorithms)”, University proceedings. Volga region. Physical and mathematical sciences, 2012, no. 1, 31–43
2011
22.
B. Melnikov, A. A. Melnikova, University proceedings. Volga region. Physical and mathematical sciences, 2011, no. 4, 59–69
B. Melnikov, “Once more on the edge-minimization of nondeterministic finite automata and the connected problems”, Fundamenta Informaticae, 104:3 (2010), 267–283
B. Melnikov, S. Pivneva, O. Rogova, “Reprezentativnost sluchaino sgenerirovannykh nedeterminirovannykh konechnykh avtomatov s tochki zreniya sootvetstvuyuschikh bazisnykh avtomatov”, Stokhasticheskaya optimizatsiya v informatike, 2010, no. 6, 74–82
26.
S. Baumgertner, B. Melnikov, “Multievristicheskii podkhod k probleme zvëzdno-vysotnoi minimizatsii nedeterminirovannykh konechnykh avtomatov”, Vestnik Voronezhskogo gos. univ., ser. Sist. analiz i inf. tekhn., 2010, no. 1, 5–7
27.
B. Melnikov, S. Eirikh, “Podkhod k kombinirovaniyu nezavershënnogo metoda vetvei i granits i algoritma imitatsionnoi normalizatsii”, Vestnik Voronezhskogo gos. un-ta, ser. Sist. analiz i inf. tekhn., 2010, no. 1, 35–38
28.
B. Melnikov, M. Zubova, “Postroenie avtomata COM na osnove bazisnogo avtomata”, Vektor nauki Tolyattinskogo gosudarstvennogo universiteta, 2010, no. 4, 30–32
29.
B. Melnikov, S. Pivneva, “Matematicheskoe modelirovanie prinyatiya reshenii v razlichnykh predmetnykh oblastyakh”, Vektor nauki Tolyattinskogo gosudarstvennogo universiteta, 2010, no. 2, 10–14
2009
30.
E. Borisova, B. Melnikov, “Approksimatsionnye algoritmy i psevdometricheskii variant zadachi kommivoyazhera”, Izv. vuzov (Povolzhskii region), fiz.-mat. nauki, 2009, no. 3, 96–100
31.
B. Melnikov, M. Saifullina, “Some algorithms for equivalent transformation of nondeterministic finite automata”, Russian Math. (Iz. VUZ), 53:4 (2009), 54–57
32.
B. Melnikov, Nedeterminirovannye konechnye avtomaty (monografiya), izd-vo Tolyattinskogo gos. univ., Tolyatti, 2009, 160 pp.
33.
E. S. Borisova, B. Melnikov, “Approximation algorithms and a pseudometric version of the traveling salesman problem”, University proceedings. Volga region. Physical and mathematical sciences, 2009, no. 3, 96–100
2008
34.
M. Alëkhina, A. Lysenko, B. Melnikov, “Ob odnom podkhode k modelirovaniyu vychislitelnykh ustroistv”, Izv. vuzov (Povolzhskii region), fiz.-mat. nauki, 2008, no. 2, 2–7
2007
35.
B. Melnikov, “On an expansion of nondeterministic finite automata”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 24:1-2 (2007), 155–165
36.
B. Melnikov, E. Melnikova, “Some competition programming problems as the beginning of artificial intelligence”, Informatics in Education, 6:2 (2007), 385–396
37.
B. Melnikov, E. Melnikova, “Some more on the billiard languages and corresponding forbidden languages”, International Conference on Infinity in Logic & Computation (Cape Town, November 2007), Univ. of Cape Town, 2007, 34
38.
B. Melnikov, E. Melnikova, “Klasterizatsiya situatsii v algoritmakh realnogo vremeni dlya zadach diskretnoi optimizatsii”, Sistemy upravleniya i informatsionnye tekhnologii, 2007, 16–19
39.
B. Melnikov, E. Melnikova, “Klasterizatsiya situatsii v algoritmakh realnogo vremeni v nekotorykh zadachakh diskretnoi optimizatsii”, Izv. vuzov (Povolzhskii region), estestvennye nauki, 2007, 3–11
2006
40.
B. Melnikov, “Multiheuristic approach to discrete optimization problems”, Cybernetics and Systems Analysis, 42:3 (2006), 335–341
41.
B. Melnikov, A. Radionov, A. Moseev, E. Melnikova, “Some specific heuristics for situation clustering problems”, (http://www.informatik.uni-trier.de/), ICSOFT (Setúbal, Portugal, September 11-14, 2006), INSTICC Press, ISBN 972-8865-69-4, 2006, 272–279
42.
B. Melnikov, A. Radionov, V. Gumayunov, “Some Special Heuristics for Discrete Optimization Problems”, (http://www.informatik.uni-trier.de/), ICEIS (Paphos, Cyprus, May 23-27, 2006), Paphos University, ISBN 972-8865-41-4, 2006, 360–364
2005
43.
B. Melnikov, “Discrete optimization problems – some new heuristic approaches”, Proceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region, IEEE Computer Society Washington, 2005, 73–80
2004
44.
B. Melnikov, “Description of special submonoids of the global supermonoid of a free monoid”, Russian Math. (Iz. VUZ), 48:3 (2004), 42–51
B. Melnikov, A. Melnikova, “A new algorithm of constructing the basis finite automaton”, Informatica (Lithuanian Acad. of Sciences), 13:3 (2002), 299–310
48.
B. Melnikov, N. Sciarini-Guryanova, “Possible edges of a finite automaton defining a given regular language”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 9:2 (2002), 475–485
49.
B. Melnikov, A. Melnikova, “Some properties of the basis finite automaton”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 9:1 (2002), 131–150
50.
B. Melnikov, “On $\omega$-languages of special billiards”, Discrete Math. Appl., 12:5 (2002), 501–514
2001
51.
B. Melnikov, “Heuristics in programming of nondeterministic games”, Program. Comput. Softw., 27:5 (2001), 277–288
52.
B. Melnikov, A. Melnikova, “Edge-minimization for non-deterministic finite automata”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 8:3 (2001), 469–479
53.
B. Melnikov, N. Romanov, “Eschë raz ob evristikakh dlya zadachi kommivoyazhëra”, Teoreticheskie problemy informatiki i eë prilozhenii, v. 4, Izd-vo Saratovskogo gos. univ., Saratov, 2001, 81–92
2000
54.
A. Brosalina, B. Melnikov, “Commutation in global supermonoid of free monoids”, Informatica (Lithuanian Acad. of Sciences), 11:4 (2000), 353–370
55.
B. Melnikov, E. Kashlakova, “Some grammatical structures of programming languages as simple bracketed languages”, Informatica (Lithuanian Acad. of Sciences), 11:4 (2000), 441–454
56.
B. Melnikov, “Once more about the state-minimization of the nondeterministic finite automata”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 7:3 (2000), 655–662
57.
A. Lozovoy, B. Melnikov, A. Radionov, “The use of genetic algorithms and specific unmatched v-filters for BPSK signals correlation noise minimizing”, Digital Signal Processing and its Applications (Moscow, 2000), v. 1, 2000, 147–149
1999
58.
B. Melnikov, “A new algorithm of the state-minimization for the nondeterministic finite automata”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 6:2 (1999), 277–290
59.
B. Melnikov, “$2\omega$-finite automata and sets of obstructions of their languages”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 6:3 (1999), 565–574
1998
60.
B. Mel'nikov, A. Radionov, “A choice of strategy in nondeterministic antagonistic games”, Program. Comput. Softw., 24:5 (1998), 247–252
61.
B. Melnikov, A. Vakhitova, “Some more on the finite automata”, J. of Applied Math. and Computing (The Korean J. of Computational and Applied Math.), 5:3 (1998), 495–506 (http://www.springerlink.com/content/1598-5865/5/3/)
1996
62.
B. Melnikov, “Algoritm proverki ravenstva beskonechnykh iteratsii konechnykh yazykov”, Vestnik Mosk.un-ta, ser. Vychisl. matem. i kib-ka, 1996, no. 4, 49–54
63.
B. Melnikov, “Variatsii na temu perebora”, Informatika i obrazovanie, 1996, no. 4, 37–45
1995
64.
B. Melnikov, “Some equivalence problems for free monoids and for subclasses of the CF-grammars class”, Number theoretic and algebraic methods in computer science, World Sci. Publ., 1995, 125–137
65.
O. Dubasova, B. Mel'nikov, “On an extension of the class of context-free languages”, Program. Comput. Softw., 21:6 (1995), 299–306
66.
B. Melnikov, Podklassy klassa kontekstno-svobodnykh yazykov (monografiya), izd-vo MGU, Moskva, 1995, 174 pp.
1994
67.
B. Melnikov, “Nekotorye problemy ravenstva v globalnom nadmonoide svobodnogo monoida”, Fundamentalnye problemy matematiki i mekhaniki (programma "Universitety Rossii"), MGU, Moskva, 1994, 304–305
1993
68.
B. Melnikov, “The equality condition for infinite catenations of two sets of finite words”, Int. J. of Found. of Comp. Sci., 4:3 (1993), 267–274
2024
Contact us: