Completeness Problem in Preserving Denotations Function Class on Records




Completeness problem, Denotations, Primitive program algebras


Background. Modern range of IT problems forces researchers to not only consider solutions of programmers’ problems, but processes of their solution. That is why researches of generally valid organization structures of the processes become the most important. Distinct place in the researches take problems related with building of algebraic characteristics of pragmatically-conditioned function classes, including completeness problems solutions in corresponding algebras.

Objective. Solution of completeness problem for class of computable manipulative functions on records. Term “manipulative” is specified as property of function to preserve denotations (atomic elements, which form records).

Methods. Primitive program algebra (PPA) has been chosen as instrument for the research of this class of computable functions. Solution of PPA completeness problem for manipulative functions on n-tuples formed solution basis of completeness problem and basis of generative functions system creation. Buildings, made in the paper, are based on algebraic methods of program analysis and methods of compositional programming.

Results. Solution of completeness problem for class of computable manipulative functions on records is described.

Conclusions. Results yielded may be utilized for further theoretical and applied researches of record manipulation methods, uncovering algebraic characteristics of manipulation functions classes on perspective carriers, for instance, lists, stacks, queues etc., programming languages semantics formalization, which use records as data type.

Author Biographies

Тарас Леонідович Захарченко, NTUU KPI

Zakharchenko Taras,

PhD student at Department of design of electronic digital equipment of National Technical University of Ukraine “Kyiv Polytechnic Institute”, Kyiv.

Business address - 01037, Kyiv, Permohy av., 37, faculty of electronic

Research interest: adaptive design  environments, image processing, artificial intelligence, digital hardware design.

Home address: 03057, Kyiv, Dovzhenka str., 14, app. 149.

tel.:  +380639602296, +380442773748.

Ігор Володимирович Редько, NTUU KPI

Redko Igor,

professor of the Chair of constraction of electronic computer apparatus of National Technical University of Ukraine “Kyiv Polytechnic Institute”, Kyiv

Business address - 01037, Kyiv, Permohy av., 37, faculty of electronic

Research interest: the theory of descriptive environments and applications of it.

Home address: 04213, Kyiv, Prirechnaya str., 19-g, app. 178

tel.: off. 477-10-60, mob. 0674455729, h. 4149153


I.A. Basarab et al., Compositional Databases.Kyiv,Ukraine: Lybid, 1992, 192 p. (in Russian).

V.N. Redko, “Basics of compositional programming”, Programmirovanie, no. 3, pp. 3–13, 1979 (in Russian).

V.N. Redko and I.V. Redko, “Existential basis of compositional paradigm”, Kibernetika i Systemnyi Analiz, no. 2, pp. 3–12, 2008 (in Russian).

V.N. Redkon and I.V. Redko, “Descriptological environment of Information Technologies”, Problemy Programmirovania, no. 2-3, pp. 65–73, 2004 (in Russian).

V.N. Redko et al., “Descriptive systems: conceptual basis”, Problemy Programmirovania, no. 2-3, pp. 75–80, 2006 (in Russian).

D.B. Bui and I.V. Redko, “Primitive program algebras of functions, which preserve denotations”, Doklady AN Ukrainy, no. 9, pp. 66–68, 1988 (in Russian).

I.A. Basrab and V.N. Redko, “Data bases from logic-functional point of view”, Programmirovanie, no. 2, pp. 53–67, 1984 (in Russian).

T.L. Zakharchenko et al., “Primitive programming algebra: general approach to a problem of functional fullness”, Nukovi Visti NTUU KPI, no. 2, pp. 29–40, 2015 (in Ukrainian).

A.I. Maltsev, “Constructive algebras. 1”, Uspehi Mat. Nauk, no. 3, vol. 16, pp. 3–60, 1961 (in Russian).

B.V. Gubsky et al., “Computable functions on relations and tables in countable and finite alphabets”, Doklady AN Ukrainy, no. 10, pp. 74–76, 1988 (in Russian).

D.B. Bui and I.V. Redko, “Completeness problems in classes of computable functions preserving denotations”, Programmirovanie, no. 4, pp. 56–67, 1991 (in Russian).

A.I. Maltsev, Algorithms and Recursive Functions.Moscow,USSR: Nauka, 1965, 391 p. (in Russian).

A.I. Maltsev, Algorythmic Systems.Moscow,USSR: Nauka, 1970, 392 p. (in Russian).

I.V. Redko and N.M. Snigur, “Algebraic characteristics of graph transformers class, which preserve denotations”, Registratsia, Khranenie i Obrabotka Dannykh, vol. 12, no. 4, pp. 54–61, 2010 (in Russian).

A.V. Gorelov et al., “Compositional basics of programmer’s activity”, in Proc. 8th Int. Conf. “Instrumentation: State and Perspectives”,Kyiv,Ukraine, 2014, p. 110 (in Ukrainian).

D.B. Bui, “Primitive programming algebras”, Ph.D. dissertation, T. Shevchenko Kyiv National University, Kyiv, Ukraine, 1984 (in Russian).