Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

4ЭО П. Фишер, А. Мейер, А. Розенберг
Очевидно, //U/C есть язык Lm+n теоремы 5.1, и, следовательно, он принадлежит Открытая проблема. Справедлив ли аналог теоремы 5.6 для ТМ?
ЛИТЕРАТУРА
1 С о b h a m A , Time and memory capacity bounds for machines, which recognize squares or palindromes, IBM Research Report RC-1621, 1966.
2. F i s h e r P. C., Turing machines with restricted memory access, Informa,-tion and Control, 9 (1966), 364—379.
3. F i s h e r M. J., Rosenberg A. L., Real-time solutions of the origin-crossing problem, Math. Systems Theory, 2 (1968), 257—263. (См. стр. 372—379 настоящего сборника.)
4. G i n s b u r g S., The mathematical theory of context-free languages, McGraw-Hill, New York, 1966. (Русский перевод: Гинзбург С., Математическая теория контекстно-свободных языков, «Мир», М., 1970.)
5. Ginsburg S., Spanier E. H., Bounded ALGOL-like languages, Trans. Amer. Math. Soc., 113 (1964), 333—368.
.6 Hart man is J., Stearns R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117 (1965), 285—306 (Русский перевод: Хартманис Дж., Стирнз Р. Е , О вычислительной сложности алгоритмов, Кибернетический сборник (новая серия), вып. 4, 1967.)
7. L a i n g R., Realization and complexity of commutative events, Univ. of Mich. Technical Report 39105-48-T, 1967.
8. Mi n sky M., Recursive unsolvability of Post's problem of tag and other topics in the theory of Turing machines, Ann. of Math., 74 (1961), 437—455.
9 Oettinger A. G., Automatic syntactic analysis and the pushdown store, Proc. 12th Ann. Sympos. in Appl. Math., 1960, 104—129.
10 Parikh R. J., On context-free languages, /. Assoc. Comput. Mach., 13 (1966), 570—581.
11. Rabin M. O., Real-time computation, Israel J. Math., 1 (1963), 203—211. (См. стр. 156—157 настоящего сборника.)
12 Rabin M. O, Scott D., Finite automata and their decision problems IBM J. Res. Develop., 3 (1959), 114—125. (Русский перевод: Р а б и н М. О., Скотт Д., Конечные автоматы и проблемы их разрешения, Кибернетический сборник, вып. 4, ИЛ, М., 1962.)
"13 Rosenberg A. L., Real-time definable languages. /. Assos. Comput. Mach., 14 (1967), 645—662. (См. стр. 168—193 настоящего сборника.)
14. Stearns R. E., H a r t m a n i s J., Lewis P., Hierarchies of memory-limited computations, Proc. 6th Ann. Sympos. Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1966, 179—190. (См. стр. 301—319 настоящего сборника.)
.15*. Ginsburg S., Rose G., A characterization of machine mappings, Ca-nad. J. Math., 18, № 2, 381—388. (Русский перевод: Кибернетический сборник (новая серия), вып. 5, 1968, 128—137.)

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 401 402 403 404 405 406 407 408 409 410 420 430


Математика