Courses and Seminars :: Students and Postgraduates :: Publications
Zhuk Dmitriy
Ph.D., Junior researcher
Dmitriy was born on August 25th, 1984 in Cherepovets.
In 2001 he graduated from Vologda State School for Mathematical and Natural Sciences (VGEML)
and was admitted as student to the department of Mathematics at Moscow State University.
Since 2003 he studied in the subdepartment of Mathematical Theory of Intelligent Systems under the supervision of Prof. V.B.Kudryavtsev. In his thesis Dmitriy completely described all precomplete (maximal) classes in one important class of heterogenous functions.
In 2006 Dmitriy graduated with distinction from department of mathematics and continued his postgraduate studies in the subdepartment of Mathematical Theory of Intelligent Systems, where he did his research in Automata Theory.
He described different properties of definite automata and obtained different results about completeness
and Acompleteness problem for definite automata.
Particularly, he proved that there exists continuum of closed classes of definite automata.
In his PhD thesis D.Zhuk describes the precise
border between algorithmically unsolvable cases and algorithmically decidable cases for Acompletness problem.
Since October 2009 he holds a position of a junior researcher in the subdepartment of Mathematical Theory of Intelligent Systems
and works mostly in Clone Theory.
He considered the closure operator for predicates (or relations) and proposed
a new technique for operating with predicates. Using this technique he obtained the following results.
Dmitriy completely described the lattice of all clones of selfdual functions in threevalued logic.
Thus, the class of all selfdual functions is the first maximal (or precomplete) class in
threevalued logic except the class of all linear function that has such description.
For every minimal clone in threevalued logic
he found the cardinality of the set of all clones containing
this minimal clone.
He also proved that the following problem is decidable: given a finite relational structure S,
decide whether S admits a nearunanimity function.
This problem appeared in studying of Constraint Satisfaction Problem and was an open problem for many years.
Area of scientific interests.
Automata theory, Multivalued logic, Clone Theory, Constraint Satisfaction Problem.
Email: Написать письмо
Publications of Dmitriy Zhuk
Zhuk D.N. The cardinality of the set of all clones containing a given minimal clone on three elements.
IEEE 42st International Symposium on MultipleValued Logic, Canada 2012.
Zhuk D.N. Structure of clones in the precomplete class of selfdual functions in threevalued logic.
Doklady Mathematics. Volume 83, Number 2 (2011) pp. 254257.
Zhuk D.N. The lattice of the clones of selfdual functions in threevalued logic.
IEEE 41st International Symposium on MultipleValued Logic, Finland 2011.
Zhuk D.N. A criterion for the decidability of the Acompleteness problem for definite automata
Doklady Mathematics. Volume 84, Number 1 (2011) pp. 447449.
Zhuk D.N. The predicate method to construct the Post lattice
Discrete Mathematics and Applications. Volume 23, Issue 2. 2011 Pp. 115128
Zhuk D.N. The cardinality of the set of all clones containing a given minimal clone on three elements.
Algebra Universalis (Accepted).
Zhuk D.N. The lattice of closed classes of selfdual functions in threevalued logic (Reshetka zamknutih klassov samodvoystvennih funkciy trehznachnoy logiki.)
Izdatelstvo MGU. 2011 (in Russian)
Zhuk D.N. Cardinality of the set of all precomplete classes for definite automata.
Journal of Mathematical Sciences. Volume 169, Number 4 pp. 430434.
Zhuk D.N. On the classification of Post automaton bases by the decidability of the Acompleteness property for definite automata
Discrete Mathematics and Applications. Volume 20, Issue 3. 2010. Pp. 337355.
Zhuk D.N. Decidable cases of the Acompleteness problem for definite automata.
Moscow, Intelligent Systems (2009) 13, 273312 (in Russian).
Zhuk D.N. On undecidability of the completeness problem for definite automata.
Moscow, Intelligent Systems (2008) 12, 211228 (in Russian).
Prismotrov Yu.N., Zhuk D.N. On the completeness problem in the class of automata without feedback.
Moscow, Intelligent Systems (2007) 11, 439472 (in Russian).
Top
