Хартманис, Льюис, Стирнз (Hartmanis J., Lewis P. М. II, Stearns R. E.)

[1965] Classification of computations by time and memory requirements, Proc. IFIP Congress 65, Spartan, N. Y., 31-35.

Хартманис, Стирнз (Hartmanis J., Stearns R. E.)

[1965] On computational complexity of algorithms, Trans. Amer. Math. Soc, 117, 285-306. (Русский перевод в Кибернетическом сборнике, нов. сер., вып. 4. М., Мир, 1967, стр. 57-85.)

Хартманис, Хопкрофт (Hartmanis J., Hopcroft J. E.)

[1971] An overview of the theory of computational complexity, J. Assoc Comput. Mach., 18, №3, 444-475. (Русский перевод в Кибернетическом сборнике, нов. сер., вып. И, М., Мир, 1974, стр. 131-176.)

Хейндел, Хоровиц (Heindel L. Е., Horowitz Е.)

[1971] On decreasing the computing time for modular arithmetic, IEEE 12th Annual Symposium on Switching and Automata Theory, 126-128.

Хект (Hecht M. S.)

[1973] Global data flow analysis of computer programs, Ph. D. Thesis, Dept. Electr. Engineering, Princeton University.

Хенни, Стирнз (Hennie F. C, Stearns R. E.)

[1966] Two tape simulation of multitape machines, J. Assoc. Comput. Mach.,

13, Я» 4, 533-546. (Русский перевод в сб. «Проблемы математической логики», М., Мир, 1970, стр. 194-211.)

Хиршберг (Hirschberg D. S.)

[1973] А linear space algorithm for computing maximal common subsequences, TR-138, Comput. Sci. Lab., Dept. Electr. Engineering, Princeton University, Princeton, N. J. См. также Comm. ACM, 18, № 6 (1975), 341-343.

Холл (Hall A. D.)

[1971] The ALTRAN system for rational manipulation-a survey. Comm. ACM,

14, №8, 517-521. XoH (Hohn F. E.)

[1958] Elementary matrix algebra, Macmillan, New York.

Xoop (Hoare C. A. R.)

[1962] Quicksort, Comput. J., 5, № I, 10-15.

Хопкрофт (Hopcroft J. E.)

[1971] An n log n algorithm for minimizing states in a finite automata, см. Кохави, Пац [1971], 189-196 (Русский перевод в Кибернетическом сборнике, нов. сер., вып. 11, М., Мир, 1974, стр. 177-184.)

Хопкрофт, Карп (Hopcroft J. Е., Karp R. М.)

[1971] An algorithm for testing the equivalence of finite automata, TR-71-114, Dept. Comput. Sci., Cornell University, Ithaca, N.Y.

Хопкрофт, Керр (Hopcroft J. E., Kerr L. R.)

[ 971] On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math., 20, № 1, 30-36.

Хопкрофт, Мусински (Hopcroft J. E., Musinski J.)

[ 973] Duality in determining the complexity of noncommutative matrix multiplication, Proc. 5th Annual ACM Symposium on Theory of Computing, Austin, Texas, 73-87.

Хопкрофт, Тарьян (Hopcroft J. E., Tarjan R. E.)

[1973a] Efficient planarity testing, TR-73-165, Dept. Comput. Sci., Cornell University, Ithaca, N. Y. См. также Л Assoc. Comput. Mach. 21, №4 (1974). [19736] Dividing a graph into triconnected components, SIAM J. Comput., 2, №3, 135-157.

[1973b] Efficient algorithms for graph manipulation. Comm. ACM, 16, №6, 372-378.

Хопкрофт, Ульман (Hopcroft J. E., Ullman J. D.)

[ 969] Formal languages and their relation to automata, Addison-Wesley, Reading, Mass.

[1973] Set merging algorithms, SIAM J. Comput., 2, № 4, 294-303.

Хопкрофт, Уонг (Hopcroft J. Е., Wong J. К-)

[ 974] А linear time algorithm for isomorphism of planar graphs, Proc. 6th Annual ACM Symposium on Theory of Computing, Seattle, Washington, 172-

Хорват (Horvath E. C.)

[1974] Some efficient stable sorting algorithms, Proc. 6th Annual ACM Symposium on Theory of Computing, Seattle, Washington, 194-215.

Хоровиц (Horowitz E.)

[1972] A fast method for interpolation using preconditioning. Inform. Process. Lett., I, №4, 157-163.

Xy (Hu T. C.)

[1968] A decomposition algorithm for shortest paths in a network., Operat.

Res., 16, 91-102. Xy, Таккер (Hu T. C, Tucker A. C.)

[1971] Optimum binary search trees, SIAM J. AppL Math., 21, № 4, 514-532. Хэдиан, Соубел (Hadian A., Sobel M.)

[1969] Selecting the rth largest using binary errorless comparisons. Tech. Rept.

121, Dept. of Statistics, University of Minnesota, Minneapolis. Цейтин Г. С.

°[1968l О сложности вывода в исчислении высказываний. Записки научн. семинаров Ленингр. отд. Матем. ин-та АН СССР, т. 8, 234-259. Шёнхаге (Schonhage А.)

[1971] Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform., 1, 139-144.

Шёнхаге, Штрассен (Schonhage A., Strassen V.)

[1971] Schnelle Multiplikation grosser Zahlen, Computing, 7, №3-4, 281-292.

(Русский перевод в Кибернетическом сборнике, нов. сер., вып. 10, М., Мир,

1973, стр. 87-98.) Шепердсон, Стерджис (Shepherdson J. С, Sturgis Н. Е.)

[ 963] Computability of recursive functions, J. Assoc. Comput. Mach., 10, № 2,

217-255. Штрассен (Strassen V.)

[1969] Gaussian elimination is not optimal, Numer. Math., 13, №4, 354-356.

(Русский перевод в Кибернетическом сборнике, нов. сер., вып. 7, М., Мир,

1970, стр. 67-70.)

°[1973] Vermeidung von Divisionen, J. Reine Angew. Math., 264, 184-202. [1974J Polynomials with rational coefficients which are hard to compute, SIAM J. Comput., 3, №2, 128-149.

"[1976] Computational complexity over finite fields, SIAM J. Comput. 5, № 2, 234-331.

Элгот, Робинсон (Elgot С. С, Robinson A.)

[1964] Random access stored program machines, J. Assoc. Comput. Mach., II, №4, 365-399.

Эренфойхт, Цайгер (Ehrenfeucht A., Zeiger H. P.)

[1974] Complexity measures for regular expressions, Proc. 6th Annual ACM Symposium on Theory of Computing, Seattle, Washington, 75-79.

Янгер (Younger D. H.)

[1967] Recognition of context-free languages in time я. Inform, and Contr., 10, № 2, 189-208. (Русский переводе сб. «Проблемы математической логики», М., Мир, 1970, стр. 344-362.)

ГЛОССАРИЙ

exclusive or -

false for goto HALT if ... then in

JGTZ

JUMP JZERO

LOAD MULT

otherwise

исключающее или (разделительная дизъюнкция, или сложение по модулю два) ложь, ложный для

то же, что go to-перейти к остановиться (команда остановки) если ... то в

сокращение от jump on greater than zero-перейти (к указанной команде), если (содержимое сумматора) больше нуля, -перейти (безусловный переход) сокращение от jump on zero (разъясняется аналогично JGTZ, но переход при равенстве содержимого сумматора нулю)

сокращение от left-влево (сдвиг головки влево) загрузить (вызов в сумматор) сокращение от multiply-умножить (команда умножения)

•не (отрицание)

•в противном случае