| RUS ENG |
| Full version |
|
|
|
| PEOPLE |
| Melnikov Boris F |
|
| Professor |
| Doctor of physico-mathematical sciences (1997) |
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.
ISTINA