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


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

ГРАНИЦЫ ПАМЯТИ ДЛЯ РАЗРЕШЕНИЯ
КОНТЕКСТНО-СВОБОДНЫХ
И КОНТЕКСТНЫХ ЯЗЫКОВ1)
П. М. Льюис //, Р. Е. Стирнз, Дж. Хартманис
1. ВВЕДЕНИЕ
Важной частью теории абстрактных языков является изучение процесса обработки этих языков на машинах различных моделей. Результаты этой области не только раскрывают важные свойства языка, но и дают непосредственные приложения также в изучении языков вычислительных машин.
В настоящей работе рассматриваются проблемы разрешения контекстно-свободных и контекстных языков машинами различного устройства.
Будем говорить, что машина разрешает данный язык, если, как только цепочка символов размещается на ее ленте ввода, машина обрабатывает эту цепочку и обязательно останавливается, выдавая «да», если цепочка содержится в языке, и «нет» в противном случае.
Опыт показывает, что некоторые языки существенно сложнее для разрешения, чем другие, и что эта сложность может сильно зависеть от устройства обрабатывающей машины.
Сложность вычисления можно измерять различным образом. В этой работе мы используем как меру сложности объем памяти, необходимой для вычисления; более точно ?(п)-ленточная мера сложности определена в [1]. Чтобы изучить зависимость этой меры сложности от устройства машины, рассмотрим четыре модели машин, определенные в [1], а именно: двустороннюю и одностороннюю машины Тьюринга, двустороннюю и одностороннюю магазинные машины. Если какая-либо из этих машин разрешает данный язык и обрабатывает каждое вводное слово длины п, используя не более L(n) квадратов своей рабочей ленты, то будем называть этот язык /.(п)-ленточно разрешимым или просто L(n)-разрешимым. Так как мы изучаем ленточные функции с точки зрения скорости роста, мы ограничимся монотонными неубывающими ленточными функциями.
Результаты [1] позволяют естественнно ввести частичное упорядочение «-^-» ленточных функций. Будем писать L(n)^-Q(n)
') Lewis II P. M., Stearns R. E., Hartmanis J., Memory bounds for recognition of context-free and context-sensitive languages, IEEE Conf. Rec. Switch Circuit Theory and Logic. Design, N. Y., 1965, 191—202.

 

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 321 322 323 324 325 326 327 328 329 330 340 350 360 370 380 390 400 410 420 430


Математика