Completeness Problem in Preserving Denotations Function Class on Records

Authors

DOI:

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

Keywords:

Completeness problem, Denotations, Primitive program algebras

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.

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

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

Downloads

Published

2015-11-02

Issue

No. 5 (2015): Engineering

Section

Art

License

Copyright (c) 2017 NTUU KPI Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work