Mykola (Nikolaj) Stepanovich Nikitchenko

Prof. Dr. Mykola (Nikolaj) Stepanovich Nikitchenko
Chairman of the Department of Theory of Programming
of the Faculty of Cybernetics
at the National Taras Shevchenko University of Kyiv.

See below:
Short C.V.
Membership, Positions, Participation in Projects
Scientific Interests
Main Publications


Born: 1951, Berdichev, Ukraine
Student: Kiev Taras Shevchenko State University, Faculty of Mechanics and Mathematics (1968 – 1969), Faculty of Cybernetics (1969 – 1973)
Candidate of physics and mathematics (Ph.D) and Doctor of physics and mathematics by speciality “Mathematical and program software of computers and systems”
Employment: Kiev State University, Faculty of Cybernetics,
Department of Programming Theory:
since 1973 on positions of Assistant Professor, Lecturer, Associate Professor.
Now Professor, Chairman of the department.


Improvement in skill:
  • Institute of Cybernetics (Kiev, 1976),
  • Novosibirsk State University (Novosibirsk, 1982),
  • Institute of software systems (Kiev, 2001)
  • Member of Working Group “Theoretical Computer Science” of Soviet Academy of Sciences (1986-1991)
  • Member of the VDM’90 Program Committee (Kiel, Germany)
  • Member of the Program Committee of World Congress on Formal Method (1999)
  • Member of the Program Committee of the East-European Conference on Advances in Databases and Information Systems (ADBIS) (since 1995)
  • Member of the Editorial Board of “The Journal of Logic and Algebraic Programming” (North-Holland).
  • Co-chairman of the Ukrainian Sub-committee of the CS IEEE (1992-1996)
  • Member of the European Association for Theoretical Computer Science (EATCS)
  • Member of the Association for Symbolic Logic (ASL)
Positions in foreign institutes:
  • Visiting researcher of the International Institute for Software Technology of the United Nations University (UNU/IIST, 1996)
  • Guest Professor of the Technical University of Denmark (DTU, 1997-1998).
Participation in INTAS Projects:
  • INFOSEM Project No 94-1817 (1995-1998)
  • “Weak Arithmetics” Project No 2000-447 (2001-2004)
  • Kiev, Moscow, Novosibirsk (since 1973),
  • Tech. Univ. of Denmark – 1989, 1997, 1998,
  • Hamburg Univ. – 1990,
  • Kiel Univ. – 1990, 1999,
  • Dagstuhl Sem. – 1992,
  • Warsaw Univ. – 1992,
  • Klagenfurt Univ. – 1994.
  • UNU/IIST – 1996,
  • Amsterdam Univ. – 1999,
  • Muenster Univ. – 2002.

Main Scientific Interests

  • formal models of programs;
  • programming and specification languages;
  • formal methods of program development;
  • predicate logics of various abstraction levels;
  • abstract computability.

The investigations are based on the notion of Composition Nominative Systems (CNS), which can be considered as adequate models of programs of various levels of abstraction and generality. These systems are constructed in accordance with the following main principles. Development Principle (from abstract to concrete): The notion of program should be introduced as a process of its development which starts from abstract understanding capturing essential program properties and proceeds to more and more concrete considerations, thus gradually revealing the notion of program in its richness. Compositionality Principle: Programs can be considered as functions which map input data into results, and which are constructed from simpler programs (functions) with the help of special operations, called compositions. Nominativity Principle: Structures of programs and data are based on nominative (naming) relations. In accordance with these principles, CNS can be defined as a unity of compositional, descriptive and denotational systems. The first system describes considered sets of data, functions and compositions, the second – sets of descriptions (expressions, formulas), and the last – denotational relations between descriptions and functions. Specific features of CNS in comparison with other models of programs are clear definitions of abstraction levels and program notions corresponding to these levels, usage of nominative relations as the only primitives in data constructions, detailed investigation of classes of compositions for various levels of abstractions. Three types of CNS are investigated, which correspond to abstract, Boolean and nominative levels in data considerations. Systems of the last type are very expressive and are used to construct formal definitions of specification, programming and database languages. The main problems studied for CNS are various completeness problems, especially problems of computational completeness. Special notions of abstract computability over various data structures – natural computability of functions and determinant computability of compositions – are introduced, complete classes of computable functions and compositions of abstract, Boolean and nominative types are defined, and their algebraic representations are constructed. For example, in the simple case of functions over nominative data built on a finite set of names V and arbitrary set of basic values W (such nominative data correspond to finite trees with branches labeled by elements of V and leaves labeled by elements of W), the complete class of such naturally computable functions precisely coincides with the class of functions obtained by closure of naming, denaming and checking functions under multiplication, iteration and overlaying compositions. CNS, which were primarily oriented on programming, can be also considered in a more general setting as formal models of languages of functional types. In particular, CNS can be used in logic to model its languages. Classical logic is oriented on n-ary total one-valued (deterministic) predicates and functions. Instead of this class of mappings we consider more powerful classes of nominative partial many-valued (non-deterministic) functions and predicates. In this case logical connectives and quantifiers can be defined as special compositions. In accordance with the principle of development we consider the following three types of logics: with abstract data (which corresponds to propositional logic), with flat nominative data (which corresponds to predicate logic), and with hierarchical nominative data. In the first case complete classes of compositions over partial and non-deterministic predicates are defined, their algebraic representations are constructed, and complete infinitary propositional equational logic for such classes are described. In the second case we construct a complete predicate logic which is a generalization of classical predicate logic and which is oriented on partial predicates over flat nominative data. In the third case we construct a special logic of hierarchical nominative data in the style of Kripke-Platek theory of admissible sets. A transport domain is another application of CNS. We define the following basic abstractions of the domain: transport objects, “take” relation of objects, and movement of objects. It turns out that formalization of these abstractions leads to such states of the domain which are described by nominative data. This fact directly permits to use CNS to represent domain transformations which reflect movement of objects of the domain. A special axiomatic system is constructed which can represent all naturally computable transformations of the domain. Thus, CNS can be considered as simple but powerful formal models of programs which are also applicable to some other important problem domains.

Traditional opinion that mathematical logic and computability theory form a basis of theory of programming tacitly implies that three theories are independent disciplines. The independence of these disciplines is supported by many circumstances. Even from historical point of view, mathematical logic and computability theory were created in their main features long before programming made its first steps. Also in the university curricula these disciplines basically are presented as independent with their own subjects and methods. But nowadays logic is widely used in practically all branches of computer science and programming. And this circumstance leads to the conclusion that mathematical logic, computability theory and theory of programming form a natural union which has to be presented as an integrated mathematical theory of logic, computability and programming. We propose to consider the notion of composition nominative system as a formal basis for unifying mathematical logic, computability theory and theory of programming.

Selected Publications
(Papers, published in the “Programmirovanie”, “Kibernetika” and “Kibernetika i sistemny analiz” Journals were translated into English by Plenum Publishing Corporation, New York):

  1. N.S.Nikitchenko, S.S.Shkilniak, Top-down syntactic analysis of programming languages, Programmirovanie, No 6, 3-11, 1975 (In Russian)
  2. N.S.Nikitchenko, Composition semantics of programming languages, Programmirovanie, No 6, 9-18, 1982 (In Russian)
  3. N.S.Nikitchenko, S.S.Shkilniak, Definitors of programs, Programmirovanie, No 1, 3-10, 1983 (In Russian)
  4. N.S.Nikitchenko, Computable compositions and universal imperative program logic, Programmirovanie, No 1, 3-14, 1983 (In Russian)
  5. N.S.Nikitchenko, V.N.Red’ko, Composition and functional programming: a comparative analysis, Programmirovanie, No 2, 15-28, 1985 (In Russian)
  6. N.S.Nikitchenko, Compositions of programs inducing monotone functions of special kind, Programmirovanie, No 1, 3-17, 1987 (In Russian)
  7. V.N.Red’ko, N.S.Nikitchenko, Composition aspects of programmology, Kibernetika, part 1, No 5, 49-56, 1987, part 2, No 1, 28-34, 1988 (In Russian)
  8. N.S.Nikitchenko, Semantic construction of programs by matching compositions, Programmirovanie, No 6, 14-27, 1987 (In Russian)
  9. N.S.Nikitchenko, G.G.Trubchaninov, Polymorphic program models, Kibernetika, No 1, 39-46, 1987 (In Russian)
  10. I.A. Basarab, N.S.Nikitchenko, V.N.Red’ko, Composition databases, Kiev, Lybid’ Publ, 1992, p. 192 (In Russian)
  11. V.Y.Zadorozhny, N.S.Nikitchenko, Algebraic approach to formalization of deductive database query languages, Programmirovanie, No 6, 29-47, 1992 (In Russian)
  12. N.S. Nikitchenko, Abstract Computability over Various Data Structures, Dagstuhl Seminar reports, Saar, Germany January, 1992.
  13. V.I.Zadorozhny, L.A.Kalinichenko, N.S.Nikitchenko, Mutually complementary formalizations of deductive query languages, Kibernetika i sistemny analiz, No 2, 94-110, 1993 (In Russian)
  14. L.A. Kalinichenko, N.S. Nikitchenko, V.I. Zadorozhny, Application of composition development method for definition of SYNTHESIS information resource query language semantics, FME’93 Symposium, Odense, Denmark, Springer Verlag, 1993.
  15. I.A.Basarab, B.V.Gubsky, N.S.Nikitchenko, V.N.Red’ko, Composition models of databases. Extending Inf. Syst. Technology, II Int. East-West Database Workshop, Sept. 25-28, 1994, Klagenfurt, Austria, 155-163, 1994.
  16. I.A.Basarab, B.V.Gubsky, N.S.Nikitchenko, V.N.Red’ko, Principles of composition database model construction, Upravliaiuschie systemy i mashiny, No 6, 31-37, 1994 (In Russian)
  17. N.S.Nikitchenko, Object-oriented generalization of composition database models, Upravliaiuschie systemy i mashiny, No 6, 48-53, 1994 (In Russian)
  18. I.A.Basarab, B.V.Gubsky, N.S.Nikitchenko. Composition approach to systematic development of database systems, In Proc. ADBIS’95, London: Springer, pages 12-23, 1995.
  19. N.S.Nikitchenko, Construction of composition systems on a base of identified data, Kibernetika i sistemny analiz, No 6, 38-44, 1995 (In Russian)
  20. I.A.Basarab, B.V.Gubsky, N.S.Nikitchenko, Declarative Languages of Composition Database Development Method. In Proc. ADBIS’96, vol. 1, Moscow, 52-56, 1996.
  21. N.S.Nikitchenko, Towards foundations of the general theory of transport domains, UNU/IIST report No 88, Macau, 37 pages, 1996
  22. N.S.Nikitchenko, Abstract transport models construction on a base of composition programming systems, Problems of Programming, No 2, 20-26, 1997 (In Russian)
  23. B.S.Hansen, N.S.Nikitchenko, Abstract transport systems: Compositions and Description Languages. In Proc. of the First Int. Scientific and Practical Conf. on Programming UkrPROG’98, Ukraine, Kiev, 59-67, 1998.
  24. N.S.Nikitchenko, A Composition Nominative Approach to Program Semantics, Technical Report IT-TR: 1998-020, Technical University of Denmark, 1998, 103 p.
  25. N.S.Nikitchenko, S.S.Shkilniak, Algebras of equitone functions and their properties, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 2, 222-232, 1998 (In Ukrainian)
  26. N.S.Nikitchenko, S.S.Shkilniak, Principles of Sigma-reflection and Sigma-parameterization in the logics of structured data, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 4, 169-179, 1998 (In Ukrainian)
  27. N.S.Nikitchenko. Composition nominative approach to the explication of the notion of program, Problems of Programming, No 1, 16-31, 1999 (In Russian)
  28. N.S.Nikitchenko, Predicate composition nominative systems, Problems of Programming, No 2, 3-19, 1999 (In Russian)
  29. N.S.Nikitchenko, Propositional compositions of partial predicates, Kibernetika i sistemny analiz, No 2, 3–19, 2000 (In Russian)
  30. N.S.Nikitchenko, S.S.Shkilniak, Composition nominative logics of equitone predicates, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 2, 300-314, 2000 (In Ukrainian)
  31. N.S.Nikitchenko, Computability of non-deterministic programs over nominative data, Problems of Programming, No 1-2, 49-62, 2000 (In Russian)
  32. N.S.Nikitchenko, L.L.Omel’chuk, S.S.Shkilniak, O.I.Yanchenko, Axiomatic systems of specification of programs over nominative data, Problems of Programming, No 1-2, 259-272, 2000 (In Russian)
  33. N.S.Nikitchenko, Applicative compositions of partial predicates, Kibernetika i sistemny analiz, No 2, 14–33, 2001 (In Russian)
  34. N.S.Nikitchenko, S.S.Shkilniak, Semantic aspects of post-classical logics, Problems of Programming, No 1-2, 3-12, 2001 (In Russian)
  35. N.S.Nikitchenko, S.S.Shkilniak, Composition nominative first-order logics, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 1, 260-274, 2001 (In Ukrainian)
  36. N.S.Nikitchenko, S.S.Shkilniak, N.V.Virych, Investigation of properties of pure neo-classical calculi, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 2, 297-301, 2001 (In Ukrainian)
  37. N.S.Nikitchenko, S.S.Shkilniak, Composition nomiminative first-order calculi, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 2, 302-311, 2001 (In Ukrainian)
  38. N.S.Nikitchenko, S.S.Shkilniak, Partial and modal logics – modelling means of subject domains, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 5, 138-147, 2001 (In Ukrainian)
  39. N.S.Nikitchenko, S.S.Shkilniak, Composition nominative logics of neo-classical type, Bulletin of the Kyiv National Taras Shevchenko University, Kibernetika, No 2, 48-57, 2001 (In Ukrainian)
  40. N.S.Nikitchenko, Intensional aspects of the notion of program, Problems of Programming, No 3-4, 5-13, 2001 (In Russian)
  41. N.S.Nikitchenko. Abstract Computability of Non-deterministic Programs over Various Data Structures // Perspectives of System Informatics (Proc. of Andrei Ershov Fourth Int. Conf., 2-6, July, 2001, Novosibirsk).– Lecture Notes in Computer Science, vol. 2244.– Berlin: Springer, 2001.– P. 471-484.
  42. N.S.Nikitchenko, S.S.Shkilniak, Composition nominative modal logics, Problems of Programming, No 1-2, 27-33, 2002 (In Ukrainian)
  43. N.S.Nikitchenko, S.S.Shkilniak, Logics of partial predicates as knowledge modeling means in expert systems, Bulletin of the Kyiv National Taras Shevchenko University, Kibernetika, No 3, 67-70, 2002 (In Ukrainian)
  44. N.S.Nikitchenko, Infinitary renominative logics of partial predicates, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 3, 229-238, 2002 (In Ukrainian)
  45. N.S.Nikitchenko. Logics of equitone predicates and their applications, Abstracts of contributed talks at the Logic Colloquim ’02 (Munster, Germany, August 3-9, 2002). The Bulletin of Symbolic Logic. Volume 9, Number 1, March 2003, 102-103.
  46. N.S.Nikitchenko, Infinitary equational logics of partial predicates of a singular level, Bulletin of the University of Kiev, Series: Physics & Mathematics, No 1, 2003 (In Ukrainian)
  47. N.S.Nikitchenko, Algebras of equitone predicates and their aplications, Kibernetika i sistemny analiz, No 1, 115–133, 2003 (In Russian)