Bases of complete systems of rational functions with rational coefficients

N. Ph. Alexiadis

Čebyševskij sbornik, Tome 24 (2023) no. 2, pp. 5-14.

Résumé

A functional system is a set of functions endowed with a set of operations on these functions. The operations allow one to obtain new functions from the existing ones. Functional systems are mathematical models of real and abstract control systems and thus are one of the main objects of discrete mathematics and mathematical cybernetic. The problems in the area of functional systems are extensive. One of the main problems is deciding completeness that consists in the description of all subsets of functions that are complete, i.e. generate the whole set. In our paper we consider the functional system of rational functions with rational coefficients endowed with the superposition operation. We investigate the problem of bases of complete systems, namely: Does every complete system have a (finite) basis?; For any positive integer $n$, is there a basis of a complete system consisting of $n$ functions? a number of examples of basis consisting of $n$ functions are presented explicitly $(n=1, 2, 3,\dots)$. The answers to all these questions are positive, which is the main result of this article.

Détail

Keywords: functional system, completeness problem, complete system, rational function, basis.

Bibliographie

[1] N. Ph. Aleksiadis, “On the bases of rational functions with rational coefficients”, Proc. 20th Int. Conf. “Algebra, number theory and discrete geometry: modern problems, applications and problems of history”, 2021, 80–83

[2] N. Ph. Aleksiadis, “Rational A-functions with rational co efficients”, Chebyshevskii sbornik, 23:4 (2022), 11–19 | DOI | MR | Zbl

[3] N. Ph. Aleksiadis, “Closed classes in the functional system of polynomials with real Coefficients”, Chebyshevskii sbornik, 24:1 (2023), 5–14 | DOI | MR

[4] Gavrilov G. P., “On functional completeness in countable logic”, Problems of cybernetics, 15, 1965, 5–64

[5] Gelfond A. O., Solving equations in integers, Science, M., 1978, 63 pp. | MR

[6] Kudryavtsev V. B., “On the powers of sets of discrete sets of some functional systems related to automata”, Problems of cybernetics, 13, 1965, 45–74

[7] Kudryavtsev V. B., Functional systems, Publishing House of Mekh-mat. fac. MSU, M., 1982, 157 pp.

[8] Maltsev A. I., Selected works, v. II, Publishing House “Nauka”, M., 1976, 388 pp. | MR

[9] Salomaa A., Some completeness criteria for sets of functions over a finite domain. II, Annales Universitatis Turkuensis, Series AI, No 63, Turun Yliopisto, Turku, 1963, 19 pp. | MR

[10] Chasavskikh A. A., “The problem of completeness in classes of linear automata”, Intelligent systems. Theory and Applications, 22:2 (2018), 151–154

[11] Yablonsky S. V., Introduction to discrete mathematics, Science, M., 1986, 384 pp. | MR

[12] Yablonsky S. V., “On functional completeness in three-digit calculus”, DAN USSR, 95:6 (1954), 1153–1156

[13] Yablonsky S. V., “Functional constructions in $k$-valued logic”, Proceedings of the Steklov Institute of Mathematics, 1958, 5–142 | Zbl

[14] Post E., Two-valued iterative sistems of mathematical logik, Prinston, 1941 | MR

[15] Rosenberg Y., “Uber die functionale Vollständigkeit in den mehrwertigen Logiken”, Praha, Rozpravi Ceskoslovenska Acodemie Ved., 80:4 (1970), 393

[16] Slupecki J., “Kriterium pelnosci wielowar — tosciowych systemow logiki zdan”, Comptes Rendus des Seances de la Societe des Sciences et des Lettres de Varsivie. Cl. III, 32 (1939), 102–128