Cтраница 4
Проблема эквивалентности для ( линейных) рекурсивных, схем сводится к проблеме эквивалентности для ( линейных) контекстно-свободных языков. [46]
Алгоритмы для распознавания и анализа, требующие числл шагов, пропорционального п3, приводят к вопросу о существовании контекстно-свободных языков, которые в самом деле требуют такого большого числа шагов. Получить такой результат оказывается трудно. [47]
Вследствие того что параллельную композицию двух автоматов с магазинной памятью нельзя преобразовать в другой автомат с магазинной памятью, контекстно-свободные языки не замкнуты по отношению к параллельной композиции. [48]
В этом разделе мы покажем, что двусторонние и односторонние машины Тьюринга и двусторонние магазинные машины определяют бесконечные иерархии контекстно-свободных языков. Как обсуждалось выше, односторонняя магазинная машина обладает только одним классом сложности L ( n) n и потому не определяет иерархию. Уже было показано, что машины Тьюринга включают все контекстно-свободные языки в свои иерархии. [49]
Мы высказываем гипотезу, что совокупность множеств, разрешимых двусторонними магазинными машинами, строго включается в множество контекстных языков и не содержит всех контекстно-свободных языков. [50]
Было бы интересно выяснить, верно ли утверждение, обратное ( Ь), так как тогда некоторые нерешенные проблемы формальных языков ( например, проблему эквивалентности для линейных контекстно-свободных языков) можно было бы свести к известным проблемам разрешимости для схем ( разд. [51]
В ряде работ показано, что некоторые известные задачи, например нахождение транзитивного замыкания графа [19], нахождение кратчайших путей в графе [90, 72, 64], нахождение максимального паросочетания в двудольном графе [45], распознавание контекстно-свободных языков [86], сводятся к умножению матриц и, следовательно, уменьшение сложности умножения матриц приводит к уменьшению сложности и для этих задач. В работе [51] показано, что построение характеристического полинома не сложнее по порядку, чем умножение матриц, а в [77] аналогичные результаты получены для приведения матриц к специальному виду. В [17] метод НВП-разложений ( см. разд. [52]
Класс контекстно-свободных языков является собственным подклассом класса контекстно-зависимых языков. Контекстно-свободные языки порождаются магазинными автоматами [5] и играют важную роль как синтаксические модели современных языков программирования. [53]
Наиболее удивительный результат подобного рода относится к односторонним магазинным машинам и двусторонним машинам Тьюринга. Любой нерегулярный контекстно-свободный язык, который можно вообще разрешить на односторонней магазинной машине, требует по крайней мере L ( n) ogn на двусторонней машине Тьюринга. [54]