Program algebras of recursive functions

V. D. Solov'ev

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 51 (1996) no. 4, pp. 705-722

Bibliographie

[1] Barzdin Ya. M., “Ob odnom klasse mashin Tyuringa (mashiny Minskogo)”, Algebra i logika, 1 (1962), 42–51 | MR | Zbl

[2] Glushkov V. M., “Teoriya avtomatov i formalnye preobrazovaniya mikroprogramm”, Kibernetika, 1965, no. 5, 1–9 | Zbl

[3] Glushkov V. M., Tseitlin G. E., Yuschenko E. L., Algebra. Yazyki. Programmirovanie, Naukova Dumka, Kiev, 1978 | Zbl

[4] Golunkov Yu. V., “K teorii sistem algoritmicheskikh algebr”, DAN SSSR, 232:4 (1977), 749–752 | MR | Zbl

[5] Golunkov Yu. V., “O polnote operatsii v sistemakh algoritmicheskikh algebr”, Algoritmy i avtomaty, KGU, Kazan, 1978, 11–53 | MR

[6] Golunkov Yu. V., “O predpolnykh klassakh algoritmov, sokhranyayuschikh prinadlezhnost mnozhestvu, 1”, Veroyatnostnye metody i kibernetika, no. 16, KGU, Kazan, 1980, 21–40 | MR

[7] Golunkov Yu. V., “Approksimatsionnaya polnota v algebrakh chastichno rekursivnykh funktsii i predikatov”, Kibernetika, 1987, no. 6, 26–30 | MR | Zbl

[8] Golunkov Yu. V., “Stepen nerazreshimosti problemy polnoty v algebrakh rekursivnykh funktsii”, Matem. zametki, 44:5 (1988), 620–627 | MR

[9] Golunkov Yu. V., “Polnota s zadannoi tochnostyu v funktsionalnykh sistemakh programmnogo tipa”, Diskretn. matem., 2:3 (1990), 42–49 | MR | Zbl

[10] Ershov A. P., “Operatornye algoritmy, 1”, Problemy kibernetiki, no. 3, Fizmatgiz, M., 1960, 5–48 | MR

[11] Ershov A. P., “Vychislimost v proizvolnykh oblastyakh i bazisakh”, Semiotika i informatika, 1982, no. 19, 3–53 | MR

[12] Ershov A. P., Lyapunov A. A., “O formalizatsii ponyatiya programmy”, Kibernetika, 1967, no. 5, 40–57 | MR | Zbl

[13] Zaslavskii I. D., “Graf-skhemy s pamyatyu”, Trudy MIAN, 72, 1964, 99–192 | MR | Zbl

[14] Zakharov D. A., Rekursivnye funktsii, NGU, Novosibirsk, 1970

[15] Kotov V. E., Saberfeld V. K., Teoriya skhem programm, Nauka, M., 1991

[16] Kudryavtsev V. B., Funktsionalnye sistemy, MGU, M., 1982

[17] Marchenkov S. S., “Bazisy po superpozitsii v klassakh rekursivnykh funktsii”, Matem. voprosy kibernetiki, no. 3, Nauka, M., 1991, 115–139 | MR

[18] Minskii M., Vychisleniya i avtomaty, Mir, M., 1971 | Zbl

[19] Nepomnyaschii V. A., “Kriterii algoritmicheskoi polnoty sistem operatsii”, Teoriya programmirovaniya, T. 1, VTs SOAN SSSR, Novosibirsk, 1972, 267–279

[20] Olshanskii A. Yu., “Gruppy ogranichennogo perioda s podgruppami prostogo poryadka”, Algebra i logika, 21:5 (1982), 553–618 | MR

[21] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[22] Savelev A. A., “Ob odnom sposobe opisaniya maksimalnykh podsistem algebr”, Veroyatnostnye metody i kibernetika, no. 18, KGU, Kazan, 1982, 77–83 | MR

[23] Solovev V. D., “Kriterii polnoty sistem vychislimykh funktsii i predikatov”, V Vsesoyuzn. konf. po probl. teoret. kiber., Tezisy dokl., IM SOAN SSSR, Novosibirsk, 1980, 115

[24] Solovev V. D., “Struktura zamknutykh klassov vychislimykh funktsii i predikatov”, Izv. VUZov. Matematika, 1982, no. 12, 51–56 | MR | Zbl

[25] Solovev V. D., “Polnota sistem obscherekursivnykh funktsii i predikatov. I; II”, Izv. VUZov. Matematika, 1989, no. 8, 56–63 ; No 9, 60–66

[26] Solovev V. D., “Algebraicheskie aspekty abstraktnoi teorii vychislimosti”, Matem. voprosy kibernetiki, no. 3, Nauka, M., 1991, 233–256

[27] Solovev V. D., “Vychislitelnye teorii nad algebrami”, Mezhdunarodn. konf. po algebre, IM SOAN SSSR, Novosibirsk, 1991, 135–136

[28] Solovev V. D., “Programmnye algebry rekursivnykh funktsii s dopolnitelnymi sredstvami zamykaniya”, Izv. VUZov. Matematika, 1993, no. 6, 46–52 | Zbl

[29] Solovev V. D., “Vychislimost nedeterminirovannymi programmami i poiskovaya vychislimost Moskovakisa”, Matem. zametki, 56:1 (1994), 149–152 | MR | Zbl

[30] Solovev V. D., “Programmno-zamknutye klassy obscherekursivnykh funktsii i predikatov konechnogo ranga”, Izv. VUZov. Matematika, 1993, no. 9, 45–60 | MR | Zbl

[31] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Trudy MIAN, 51, 1958, 5–142 | MR | Zbl

[32] Yanov Yu. I., “O logicheskikh skhemakh algoritmov”, Problemy kibernetiki, T. 1, Fizmatgiz, M., 1958, 75–127 | MR

[33] Aho A., Hopcroft J., Ullman J., The design and analysis of computer algorithms, Addison-Wesley, London, 1976

[34] Constable R., Gries D., “On classes of program schemata”, SIAM Comput., 1 (1972), 66–108 | DOI | MR

[35] Gordon C. E., “Prime and search computability, characterized as definability in certain sublanguages of constructible $L$”, Trans. Amer. Math. Soc., 197 (1974), 391–408 | DOI | MR

[36] Friedman H., “Algorithmic procedures, generalized Turing algorithms and elementary recursion theory”, Logic Coll.'69, North-Holland, Amsterdam, 1971, 361–389

[37] Kfoury A. J., “Definability by programs in first-order structures”, Theor. Comp. Sci., 25 (1983), 1–66 | DOI | MR | Zbl

[38] Kfoury A. J., Urzyczyn P., “Necessary and sufficient conditions for the universality of programming formalisms”, Acta Infor., 22 (1985), 347–377 | DOI | MR | Zbl

[39] Kfoury A. J., Urzyczyn P., “Concurrent program schemes”, Fundam. Infor., 10 (1987), 337–362 | MR

[40] Lerman M., Degrees of unsolvability, Springer-Verlag, Berlin, 1983 | Zbl

[41] Moshovakis Y. N., “Abstract first order computability. I; II”, Trans. Amer. Math. Soc., 138 (1969), 427–504 | DOI | MR

[42] Post E., “Two-valued iterative systems of mathematical logic”, Ann. Math. Studies, 5, Princeton, 1941 | MR | Zbl

[43] Soloviev V. D., “Nondeterministic finite algorithmic procedures as the models of abstract computability”, Lect. Notes Comp. Sci., 278, Springer-Verlag, Berlin, 1987, 409–411

[44] Soloviev V. D., “Automorphism of the program closed classes of functions and predicates structure”, Recursive Function Theory: Newsletter, 1992, no. 39 | Zbl

[45] Spepherdson L. S., “Computation over abstract structures: serial and parallel procedures and Friedman's definitional schemes”, Logic Coll.'73, North-Holland, Amsterdam, 1975, 445–513

[46] Sheperdson J. C., Sturgis H. E., “Computability of recursive functions”, Jour. ACM, 10:2 (1963), 217–255 | DOI | MR

[47] Tokura N., Kasami T., Furuta Sh., “Janov schemas augmented by a pushdown memory”, IEEE 15th Ann. Symp. Switch and Automata theory, New York, 1974, 84–94 | MR

[48] Tucker J. V., Computing in algebraic systems, Preprint series, Matem. Inst., Univ. Oslo, Oslo, 1978