Completeness Problem in Preserving Denotations Function Class on Records

Тарас Леонідович Захарченко, Ігор Володимирович Редько

Abstract


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.


Keywords


Completeness problem; Denotations; Primitive program algebras

References


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).


GOST Style Citations


  1. Басараб И.А., Никитченко Н.С., Редько В.Н. Композиционные базы данных. – К.: Либідь, 1992. – 192 с.

  2. Редько В.Н. Основания композиционного программирования // Программирование. – 1979. – № 3. – С. 3–13.

  3. Редько В.Н., Редько И.В. Экзистенциальные основания композиционной парадигмы // Кибернетика и системный анализ. – 2008. – № 2. – С. 3–12.

  4. Редько В.Н., Редько И.В. Дескриптологическая среда информационных технологий // Проблемы программирования. – 2004. – № 2-3. – С. 65–73.

  5. Редько В.Н., Редько И.В., Гришко Н.В. Дескриптивные системы: концептуальный базис // Проблемы программирования. – 2006. – № 2-3. – С. 75–80.

  6. Буй Д.Б., Редько И.В. Примитивные программные алгебры функций, сохраняющих денотаты // Докл. АН УССР. – 1988. – № 9. – С. 66–68.

  7. Басараб И.А., Редько В.Н. Базы данных с логико-функциональной точки зрения // Программирование. – 1984. – № 2. – С. 53–67.

  8. Примітивна програмна алгебра обчислювальних функцій над записами / Т.Л. Захарченко, Д.І. Редько, І.В. Редько, П.О. Яганов // Наукові вісті НТУУ “КПІ”. – 2015. – № 2. – С. 29–40.

  9. Мальцев А.И. Конструктивные алгебры. 1 // Успехи мат. наук. – 1961. – 16, № 3. – С. 3–60.

  10. Губский Б.В., Крапива Е.В., Редько И.В. Вычислимые функции на реляциях и таблицах в счетном и конечном алфавитах // Докл. АН Украины. – 1988. – № 10. – С. 74–76.

  11. Буй Д.Б., Редько И.В Проблемы полноты в классах вычислимых функций, сохраняющих денотаты // Программирование. – 1991. – № 4. – С. 56–68.

  12. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 391 с.

  13. Мальцев А.И. Алгоритмические системы. – М.: Наука, 1970. – 392 с.

  14. Редько І.В., Снігур Н.М. Алгебраїчна характеристика класу графових перетворювачів, які зберігають денотати // Реєстрація, зберігання і обробка даних. – 2010. – 12, № 4.– С. 54–61.

  15. Горєлов А.В., Редько І.В., Яганов П.О. Композиційні засади програмістської діяльності // Тези XIII Міжнар. конф. “Приладобудування: стан і перспективи”, 23–24 квітня 2014 р., Київ. – К., 2014. – C. 110.

  16. Буй Д.Б. Примитивные программные алгебры: Дис. ... канд. ф.-м. наук: 01.01.09. – К., 1984. – 150 с.




DOI: https://doi.org/10.20535/1810-0546.2015.5.50573

Refbacks

  • There are currently no refbacks.




Copyright (c) 2017 NTUU KPI