Zap. Nauchn. Sem. LOMI, 1979, Volume 88

JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

1979, Volume 88

Contents

Studies in constructive mathematics and mathematical logic. Part VIII

	A coherence theorem for canonical morphisms in cartesian closed categories A. A. Babaev, S. V. Solov'ev	3
	A machine description and a hierarchy of initial Grzegorczyk's classes A. P. Beltiukov	30
	Time bounds of multidimensional Turing machines D. Yu. Grigor'ev	47
	Two reductions of graph isomorphism to problems for polynomials D. Yu. Grigor'ev	56
	Theorems on the time hierarchy for random access machines A. G. Ivanov	62
	On decision procedures for invariant properties of short algorithms N. K. Kossovski	73
	A diophantine representation of perfect numbers V. A. Kriaučiukas	78
	Calculuses with monotone deductions and their economic interpretation S. Yu. Maslov	90
	A new reduction sequence for arithmetic G. E. Mints	106
	A primitive recursive bound of strong normalization for predicate calculus G. E. Mints	131
	Lower bounds for lengthening of proofs after cut-elimination V. P. Orevkov	137
	Three ways of recognizing essential formulas in sequents V. P. Orevkov	163
	Machine-independent description of some machine complexity classes S. V. Pakhomov	176
	Positive rudimentarity of the graphs of the Ackermann's and Grzegorczyk's functions A. V. Proskurin	186
	A growth of length of $\mathrm L$-derivationtrans formed into natural deduction S. V. Solov'ev	192
	Preservation of the equivalence of proofs under reduction of the formula depth S. V. Solov'ev	197
	Representation of proof s' by coloured graphs and Hadwiger hypothesis P. Yu. Suvorov	209
	On canonical recursive functions and operations N. A. Shanin	218

Correction
	Corrections to the previous volumes	248