Сложность множества тавтологий и некоторых родственных ему множеств тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ВВЕДЕНИЕ.

ПЛАВА. I. Мера сложности множества тавтологий и некоторых других множеств формул.

§1. Необходимое условие ограниченности меры контекстности функцией порядка о(Сод.^п)

§2. Мера правой контекстности для множества тавтологии при двоичном кодировании

§3. Мера контекстности и мера правой контекстности для множества тавтологии при унарном кодировании Зт

§4. Сигнализирующая времени для множества тавтологий и множества выполнимых формул

ГЛАВА 2. Множества СЛист., <%илт9 (ХИ7 Ын, (Хкист,01ё«т и подклассы класса языков, распознаваемого детерминиро-ванно за полиномиальное время

§1. Хорновские тавтологии

§2; 0 принадлежности множеств формул исчисления выс- с называний классам .5Ь

ГЛАВА 3. Место множества тавтологий и родственных множеств в низших классах примитивно-рекусивных множеств

§1. Рудиментарность множества тавтологий и некоторых других множеств

§2. Изословарность .¿

§3. 5 -рудиментарность.

ГЛАВА 4. О принадлежности множеств (%$ып> ОСн, Осн и некоторых подмножеств множества б1исгп классу индексных языков

§Г. Основные определения ;.Л

§2. Структура квазисовершенных дизьюктивных нормальных форм. / А А ^

§3. Множества (Х^ у (%н > (%н - индексные языки. Ю

Множество тавтологий - исключительно важный объект исследования в математической логике. В настоящее время одно из главных направлений теории алгоритмов - изучение сложности алгоритмов и вычислений. Первоначально основная проблема заключалась в исследовании вопроса:"Существует алгоритм или нет?", а теперь центр тяжести переместился к вопросу о строении алгоритмов и процессов их работы. С этой точки зрения интересно посмотреть на классические объекты математической логики - такие, как множество тавтологий. Это связано с тем, что тавтологии, как недавно Iii выяснилось, - удобный модельный объект для переборной задачи; тем самым изучение этого множества может позволить пролить некоторый свет на возможные подходы к решению этой задачи.

Цель данной работы заключается в исследовании свойств множества тавтологий и родственных множеств: множества выполнимых формул, множества хорновских тавтологий, множества формул, состоящего из всех представлений конечного числа булевых функций.

Эти множества издавна привлекали к себе внимание благодаря удивительной красоте структуры и возможности анализировать на на их основе законы и возможности логических заключений. Уже у Аристотеля была идея составлять сложные рассуждения, последовательно производя простые элементарные шаги, не зависящие от природы объектов, о которых идет речь. Дальнейшее развитие эта идея получила, в частности, у Лейбница, Буля, Гильберта. Сравнительно недавно, в 60-х годах, С.Кук Iii доказал, что множество тавтологий, равно как и множество выполнимых формул, . является хорошим модельным объектом для переборной задачи.

Интересный результат о множестве тавтологий получен Г.С.Цейтиным /2 / ; им введены некоторые величины, характеризующие сложность вывода, и установлен ряд соотношений между ними. М.В.Ломковская ¡31 установила, что множество выполнимых формул (с бесконечным списком переменных) принадлежит классу Я -языков.

В настоящей работе рассматривается множество тавтологий и родственные ему множества формул исчисления высказываний с конечным и бесконечным списком переменных элементарных высказываний. В случае конечного числа переменных используется алфавит 7, а1,.,йп,),(]. Множество тавтологий в этом алфавите обозначается через 01^ст , множество выполнимых формул - через <Э1^Ъ1П , множество формул, каждая из которых равносильна некоторой формуле данного конечного множества М -через (31 м . Для бесконечного списка переменных рассматриваются два способа кодирования: унарное, при котором переменная кодируется цепочкой а Н„.1 и используется алфавит В,= {&,У, 7, а ,'/,),( } , и двоичное - С^ кодируется цепочкой аР , где Р - двоичная запись числа I , и используется алфавит В={&, \/,э,Л ау 0» 1 >);(}£' При двоичном (унарном) кодировании мы пользуемся следующими обозначениями для множеств: (МЛ1СТПСО^с»^ — множество тавтологий, (01'^ьт) - множество выполнимых формул, &н((лн) - множество хорновских тавтологий, 01 м (СХ'дд) — множество формул, состоящее из всех представлений булевых функций из конечного множества М.

Для всех этих множеств в данной работе установлено их место в иерархии примитивно-рекурсивных множеств, получены оценки для ряда широко распространенных мер сложности, рассмотрен вопрос о принадлежности перечисленных множеств известным подклассам класса языков, распознаваемого детерминированной машиной Тьюринга за полиномиальное время; доказано, что множества ОСв¥Л , б1н7 Осн индексные языки, а (Х^^ содержит бесконечно много неиндексных языков.

В теории формальных грамматик и языков важное место занимает вопрос об устройстве "механизма", позволяющего НС-грамматике с использованием контекста порождать не бесконтекстные языки С 1Н1 ->151-, /6/,/^/). В работах Ф.Й.Бранденбурга ( /3/ , 131 , НО/ ) детально изложен один из способов исследования этого механизма, связанный с системой предков и потомков в цепочке; введены меры, которые можно интерпретировать как "меры небесконтекстности" языка. Среди них важнейшие - мера контекст-нос ти и мера правой контекстности, которые, в отличие от таких распространенных мер сложности, как время и емкость, характеризуют внутреннюю структуру вывода. Мера контекстности определяется как максимальная длина цепочек-предков для каждого вхождения символа в выводимую цепочку, определение меры правой контекстности получается из определения меры контекстности наложением некоторого ограничения на вывод.

Эти меры сложности использованы автором для характериза-ции множеств: ^ист» ^исщ » ып » ^ » ^ м » м •

В первом параграфе первой главы доказано необходимое условие мажорируемости меры контекстности функций, по порядку меньшей * Отсюда получена нижняя оценка меры контекстности для множеств 01 ист > > ^-ист •> ^м •

Во втором параграфе для названных множеств при двоичном кодировании доказано, что их мера правой контекстности не может быть ограничена сверху функцией, по порядку меньшей п.

В третьем параграфе для этих же множеств при унарном кодировании переменных установлено, что их мера контекстности не может быть ограничена сверху функцией, по порядку, меньшей 1оугп. I ГУ I

Кроме того, в этом параграфе рассмотрены множества ФисП1 и (л&ып, представляющие собой соответственно множество тавтологий и множество выполнимых формул при унарном кодировании переменных, причем для каждой формулы выполняется условие: где к - число вхождений различных элементарных переменных высказываний в формулу,п- число вхождений всех высказываний в формулу. Как следует из доказательства теоремы С.Кука в /I/, аналогичные множества при двоичном кодировании являются моделями для пере

I , борной задачи. Для $исти (Х^, установлено, что мера их контекстности и мера правой контекстности ограничена сверху функцией

Г* ,

Сод п, кроме того, мера правой контекстности для СКист не может быть ограничена сверху функцией, по порядку меньшей £од2п.

Одной из центральных задач теории сложности вычислений является установление для любого НС-языка оценки времени распознавания детерминированной или недетерминированной машиной Тьюринга и времени порождения НС-грамматикой. Для множеств ист » ^ист, 01 м 1 ^м » ^ ист > 1л эта задача особенно актуальна в связи с известной проблемой, о связи между детермированными и недетермированными вычислениями за полином-ное время /I/. Поэтому в следующем параграфе рассмотрен вопрос о сигнализирующей времени для перечисленных множеств. Установнаются детермированной машиной Тьюринга за время

Этот результат особенно интересен тем, что он является первым примером, когда оценки сложности для двоичного и унарного кодирования не совпадают.

Для двоичного кодирования доказано, что нижней оценкой времени распознания детерминированной машиной Тьюринга для (Заявляется функций п27 л 0(п-я) служит нижней оценкой времени порождения НС-грамматикой для множеств (Хцсгп и 0(м.

Вторая глава посвящена вопросу о принадлежности множеств $ ист, <*исн, а&ът, а &ът, йм,а'м, а'н, 01ист, известным подклассам класса языков, распознаваемого детерминированной машиной Тьюринга за полиномиальное время.

Установлено, что множество хорновских тавтшогий нельзя представить в виде пересечения конечного числа КС-языков.Этот результат особенно интересен в связи с тем, что, как нетрудно показать, это множество можно распознавать детерминированно за ч время п на одноленточной машине Тьюринга и за линейное время на вычислительных устройствах типа РАМ.

В настоящее время известно много классов языков,строго промежуточных между классом НС-языков и классом КС-языков; эти классы введены и подробно изучены в ряде работ многих авторов. Наиболее сложными и мало изученными почти для всех этих классов языков типов задач являются задачи о времени распознавания детерминированными (недетерминированными) автоматами из различных классов автоматов множеств данного класса. В /19/ доказано, что языки,принадлежащие классу простых матричных языков (¿зпм/20/), классу языков, порождаемых грамматиками М

Касаи степени п (¿к/21/ ), классу языкяв, порождаемых линейными КС-грамматиками с нерегулярным языком управления (¿¡¡</22/), классу векторных языков /23/ , распознаются детерминированной машиной Тьюринга за полиномиальное время. Поэтому естестI венно возникает вопрос о принадлежности множеств 0£ист(^ист)» ^Ьып(^бып) » 01М(СО ?тим классам. Для классов ¿6Пм , ¿кс » ^к автором получен отрицательный ответ на этот вопрос, что является еще одним доводом в пользу известной гипотезы С.Кука о нераспознаваемости множеств $ист и 01&ып детерминированно за полиномиальное время.

В то же время для множества тавтологий с конечным списком переменных доказано, что это множество является КС-языком (теорема А.А.Мучника) и, следовательно, распознается детермиа нированной машиной Тьюринга за время п . Этот результат распространен на множества 01^ып и 01 ^ .

В третьей главе получен новый результат о месте множеств (%ист , &ист , & &ып , С^ьт , , 01'м в иерархии классов языков, промежуточных между НС-языками и бесконтекстными. Среди этих классов одним из важнейших и интереснейших является класс рудиментарных множеств, введенный Раймондом Смальяном 124 / .

Доказано, что все перечисленные множества рудиментарны, но не 5 -рудиментарны (по Смальяну), и не являются изословар-ными (изословарные множества рассмотрены Н.К.Косовским).

Результат о принадлежности названных множеств классу рудиментарных предикатов интересен в теоретическом и прикладном аспектах в связи с тем, что, как показано в /2 5/ , рудиментарные предикаты вычисляются на простейших (абстрактных) вычислительных устройствах, очень похожих на реальные вычислительные устройства типа цифровых вычислительных машин.

Как уже было сказано, в настоящее время известно много классов НС-языков, содержащих класс контекстно-свободных языков. Один из наиболее интересных и важных классов этого рода - класс индексных языков Дхо^^/. Он замкнут относительно многих важных операций над языками и образует абстрактное семейство языков /27/.

Четвертая глава посвящена исследованию вопроса о принадлежности множеств Oigun, OiH , QLH , а -галже некоторых важных подмножеств множества (Лист С Oi'ucm. ) классу индексных языков.

Класс индексных языков довольно широк, ü ¡ZSf установлено необходимое условие принадлежности шожества этому классу. Но по этому условию примеры неиндексных языков получаются в основном однотипными: безотносительно к структуре множеств важна изменяющаяся по закону / длина слов. Первый интересный пример неиндексного языка был приведен в работе М.И.Фишера //23/. Это множество $(ctSn)m I п= Автором получено обобщение этого результата и доказано существование бесконечной последовательности неиндексных языков, представляющих собой множество формул в так называемой квазисовершенной дизъюнктивной нормальной форме (к.с.д.н.ф.), имеющих красивую и довольно богатую структуру И содержащихся в множестве СЯист^ СНист » Oin , ото существенно более сложный пример (в настоящее время единственный известный пример такого рода) неиндексных языков.

Что же касается множества выполнимых формул, то здесь автором усилен результат М.В.Ломковской и показано, что множество выполнимых формул принадлежит классу составных языков, являющемуся собственным подклассом класса индексных языков по Ахо и класса N -языков (в терминологии М.В.Ломковской),

Рассмотренные множества находят широкое применение (теоретического и прикладного характера) в качестве модельных объектов для ряда задач. Так множество (Ям общеупотребительно для описания релейно-контактных схем в случаях, когда нужно реализовать все возможные прохождения тока через цепь при данных условиях.

Рассмотренные множества используются при описании функционирования автоматов, в эвристическом программировании при организационном переиоре, когда строится граф "решений" и поиск доказательства сводится к нахождению оптимального пути-в графе.

При распознавании образов задачи описания сложных сигналов при наличии помех часто сводятся к задаче отыскания кратчайшего пути в графе, т.е. переборной задаче.

В экономических задачах, описываемых при помощи иерархи

К К ческих систем, также используются множества (Жист» ,<Ям.

Так, при построении модели решения такой глобальной задачи, как задача о взаимодействии экономических интересов отдельных личностей, коллективов и общества в целом, как было показано автором в /53/, успешное функционирование данной системы формально описывается при помощй тавтологий.

Множество хорновских тавтологий является хорошей моделью для задачи идентификации цепочек символов при редактировании текстов, поиске данных.

Поэтому исследование сложности этих множеств представляет интерес. Полученные в работе теоретические результаты, связанные с установлением ряда важных свойств рассмотренных множеств, могут найти практическое применение при решении многих прикладных задач.

Основными результатам, полученными автором являются:

1. Получено необходимое условие ограниченности меры контекстнос-ти функцией, меньшей по порядку, чем {о^1о^п/стот результат представляет для теории формальных языков самостоятельный интерес. При помощи необходимого условия доказано, что мера контекст-ности для множеств 1лцс+п> м) ^м не может быть ограничена сверху функцией, меньшей по порядку, чем

2. Установлено, что для ^цСти мера правой контекстности является максимальной, а при унарном кодировании - не может быть ограничена сверху функцией по порядку меньшей "Ц^И

3. Определено место множества тавтологий и родственных множеств в иерархии примитивно - рекурсивных множеств: доказано, что ист 1 Яцсгн, рудиментарны.

4. Доказано, что любое подмножество множества тавтологий в квазисовершенной дизъюнктивной нормальной форме, содержащее формулы, зависящие от любого числа различных элементарных переменных высказываний, не принадлежит классу индексных языков.

Результаты диссертации докладывались на семинаре по математической логике в Ленинградском отделении Математического института АН СССР, а также неоднократно докладывались на семинарах по математической логике в Калининском государственном университете.

По теме диссертации опубликовано шесть работ /30/ - /35/. В заключение хочу принести свою глубокую признательность моему учителю А.В.Гладкому, под влиянием которого сложились мои взгляды и интересы в области математики.

ЗАКЛЮЧЕНИЕ

В работе проведено исследование алгоритмической природы мнэжества тавтологий, множества выполнимых формул, множества хорновских тавтологий и множества формул, каждая из которых равносильна некоторой формуле из заданного конечного списка. Эт:я множества рассмотрены в двух вариантах: с конечным и с бесконечным списком переменных. Во втором варианте использовались два способа кодирования: унарное и двоичное. Вопрос об алгоритмической природе рассмотренных множеств, т.е. о месте этлх множеств в различных иерархиях "алгоритмически предста-вимых" множеств, актуален и представляет большой интерес как вввду очевидной важности этих множеств самих по себе, так и ввиду той роли, которую сравнительно недавно получили множества ©(.цс^ , 01 в одной из труднейших задач современной математической логики - задаче о связи между детерминированными и недетерминированными вычислениями за полиномиально ограниченное время: известно, что эта задача сводится к задаче о возможности детерминированно перечислить за полиномиальное время множество 01 ист или Этим определяется значимость и актуальность проведенных исследований.

В работе выяснено место множества тавтологий и родственных множеств в иерархии примитивно-рекурсивных множеств; при этом получен важный не только в теоретическом, но и в прикладном аспекте результат о рудиментарности рассмотренных множеств.

Для множеств (Хист , 01 ^ст , ОЦьт >

МП ' 1 м *

0(м , рассмотрены мера контекстности и мера правой контекст-ности, определенные в 191 и характеризующие степень небеско.ятекстности" языка. Для меры контекстности получено необходимое условие ограниченности ее функцией порядка 0 (£о) для произвольного НС-языка. Получены оценки этих мер сложности для всех перечисленных множеств.

Рассмотрены сигнализирующие времени распознания указанных множеств детерминированной машиной Тьюринга и порождения их НС-грамматикой. Эти вопросы особенно важны в связи с известной проблемой С.Кука.

Л» | Л/ |

Рассмотрены множества Фисти 61&ЫП , представляющие собой соответственно множество тавтологий и множество выполнимых формул при унарном кодировании, причем в каждой формуле 8-к^п, гдо к - число вхождений различных элементарных переменных высказываний, п - число вхождений всех высказываний в эту о. I п/( формулу. Доказано, что множества (Яистп и распознаются детерминированной машиной Тьюринга за время . Этот результат является первым примером неравнозначности унарного и двоичного способа кодирования. Кроме того, результат интересен тем, что, как следует из теоремы С.Кука М/, задача распознавания аналогичных множеств;при двоичн.бм кодировании переменных является универсальной переборной задачей.

В работе изучен вопрос о принадлежности множеств

X н , ИЗВвСТНЫМ ПОДкл&ссам класса языков, распознаваемого детерминирование за полиномиальное время.

Доказано существование бесконечной последовательности некндексных языков, принадлежащих множеству 0(г1Ст (0['ист). ЭтС'Т результат особенно интересен тем, что эти множества являются первым известным примером важных для математической логики множеств, имеющих красивую и довольно сложную структуру, не принадлежащих классу индексных языков и содержащихся в нерегулярном множестве. В то же время для (Х'^ доказано, что это множество принадлежит некоторому подклассу класса индексных языков.

Полученные результаты могут найти теоретическое и практическое применение, поскольку рассмотренные множества используются в широком классе математических и инженерных задач, например, в задачах описания релейно-коитактных схем, в задачах описания функционирования автоматов, в зврическом программировании, при распознавании образов, в экономических задачах, при редактировании текстов, поиске данных и других задачах.

УКАЗАТЕЛЬ ОСНОВНЫХ ОБОЗНАЧЕНИИ И СОКРАЩЕНИЙ г множество тавтологий в алфавите Ъ V, множество выполнимых формул в алфавите Ьк ; - множество формул в алфавите Ъ* , каждая из которых равносильна некоторой формуле данного конечного множества /И ; кп (^ст) ~ множество тавтологий при двоичном (унарном) копировании переменных; '¿ил) ~ множество выполнимых формул при двоичном (унарном) кодировании переменных; н ) - множество хорновских тавтология при двоичном (унарном) кодировании;

- множество п юр мул, состоящее из всех представлений булевых функций из конечного множества М при двоичном унарно м) кодировании;

- класс рекурсивно перечислимых множеств; ънс - класс детерминированных НС-языков;

- нижний [ класс иерархии Гкегорчика;

6* - класс элементарных по Сколему множеств; п * - класс рудиментарных множеств;

- класс 5 -рудиментарных множеств;

- класс изословарных множеств;

КС - класс КС-языков;

- класс индексных языков Ахо;

- класс простых матричных языков Ибарра;

К с - класс языков, порождаемых линейными КС-грамматиками с нерегулярным языком управления; - класс языков Касаи степени ¡г ; п.п.ф. - правильно построенная Формула; с.д.н.ф. - совершенная дизъюнктивная нормальная форма; к.с.д.н.ф. - квазисовершенная дизъюнктивная нормальная форма; А * - множество всех цепочек (слов) в алфавите А ; А+ - множество непустых цепочек (слов) в алфавите Д ;

- пустое слово;

- функция у (п) по порядку меньшая (¡{п) (-¿¡ж С 5 - меРа контекстности;

Сд7 - мера правой контекстности; м.о.п. - минимальная самостоятельно порождающая цепочка;

-сеУ^-а^)- отрезок вывода, начинающийся цепочкой Х£Г и заканчивающийся цепочкой "»г > 1-АРДА - магазинный автомат с вспомогательной лентой;

М( - мощность множества ; - длина цепочки; ¿тс ;

Л(О) - множество всех деревьев выводов в бесконтекстных грамматиках; К(Б) - множество всех деревьев выводов ширины к (в бесконтекстных грамматиках);

Л (46) - множество недеформированных деревьев выводов; композиция поддеревьев Т1 и Тг в узле с^ ; I - линейное множество с периодом , и предпериодом ;

Ж™ - пространство размерности п, ;

7 - целая часть х \ Сот Ск,^ г) - г -конкатенация х и & ; f10

1. COOK S.A. The Complexity of Theorem-proving Procedures.3.rd ACM Symp. on Theory of Computing, 1971, p.151-158. /Русский перевод: Кук С.А» Сложность процедур вывода теорем.-В кн.: Кибернетический сборник, 1875, вып. 12, &.5-15/.

2. ЕЕЙТИН F.C. О сложности вывода в исчислении высказываний.- Заи# научных семинаров Ленинградского отделения Матем. и»-та АНССР, 1968, т.8.

3. ЛОМКОВСКАЯ М.В. О некоторых свойствах к-условных грамматик»

4. Научно-техническая информация, 1972, HI,с.16-21,

5. LOOK R.V. Terminal Context in Context-sensitive Grammars. SJAM J.Computing, 1972, N I, p. 2050.

6. EOOK R.V. Topics in Formal Languages Theory. In:

7. Aho A.V.,ed.t Currents in the Theory of Computing, Prentice Hall, Englewood Cliffs, N.J.(1973).

8. EOOK R.V. On the Structure of Context-sensitive grammars. Interaat.J.Comput.Information Sci.1973, n.2,p.I29-139.

9. EAKER B.S. Non-context-free Grammars Generating Context-free Languages. Information Control,1974,n.24, p.231-243.

10. ERANDENBURG F.J.Fiir Verallgemeinerung von Grammatiken durch

11. BRANDENBURG F.J.On one-way Auxiliary Pushdown Automata.1.cture Notes in Computer Science, 1977, v.46, p.132-134.

12. BLÜM M. A Machine-independent Theory of the Complexity Machinery, 1967, v.14, n.2, p.322-337. /Русский перевод: Блюм M., Мапшно-не зависимая теория сложности рекурсивных функций, в сб.: Проблемы математической логики, Мир, 1970, с: 401-422/.

13. Диковский А.Я. К общему понятию сложности вывода в контекстна-свободной грамматике. Доклады АН ССР, 1974, т. 214, №2, с.257-260.

14. ГЛАДКИЙ A.B., ДИКОВСКИЙ А.Я. Теория формальных грамматики языков» в сб.: Труды 2-ой Всес. нонф- го программированию. Приглаш. докл. /1-й вып./, Новосибирск, 1570, й. 43-70.

15. INGVE "V.H. A model and hypothesis for languagestructure. Proc.Amer.Phil.Soc.,1960, v.104, П.5, p.444-466. /русский перевод: Ингве В. Гипотеза глубины* В ©б.: Новое в лингвистике, М-»Прогресс,1965, вып.4, ©.126КЕ38/.

16. CHÖblSKY N. On the notion "rule of grammar" • In:

17. Structure of Languages and its Mathematical Aspects, Providence (Rhode Island), 1961, p.6-24. /Русский перевод: Хомскжй H. О понятии, "правило; грамматики". -В сб.: Новое в лингвистике., Прогресс, 1965, вып. IУ, с.34г-65/.

18. BAR-HILLEL J. ,PERLES M.,SCHAMIR Е. Measures of syntactic

19. Complexity. Technical Rept.,I963,n.l3 /русский перевод: Бар-Хшллел И., Kastep А- Шамир В., Меры синтаксической сложности, Кибернетический сборник, нов.серия, вып.4, мир, 1967, с.219-22.7/.

20. SUDBOROUGH J.H. The Complexity of the Memberschip Problem for some Extensions of Context-free Languages, Int.J.Comput.Math.,I977»v.6, n.3,p.I9I-.215.

21. IBARRA OSCAR H. Symple Matrix Languages, Inform and

22. Contr.,1970,v.17,n.I4,p.359-397.

23. KASAI T. State Grammars and Languages. J.Comput.and Syst.Sei.,1970,v.4,p.492-508.

24. KNABSAZ NABIL A. A geometric hierarchy of languages, J.

25. Comput. and Syst.Sci., I970,v.8,n.2, p.142-157.23«. CRHMERS A.B.,MAYER 0. On vector languages, J»of Сотр.and Syst.Sci.,1974,v.8.p.I42-I57. 24. SMULLYAN R.M. Theory of formal sistems, Annals of

26. GINSBORG S.,GREIBACH S. Abstract families of languages,

27. Mem.Amer.Math.Soc.,I969,v.87,P.I-32.русский перевод: Гинзбург С. »Грейбаж ILL Абстрактные семейства языков. В кн.: Языки и автоматы, М.,МйрД9?5, <£.233-281/ .

28. HAYASKI TAKESHI: On derivation trees of indexed grammars.

29. An extension of the UVWXY-theorem,

30. Pupls.Res.Inst.Math.Sci.,I973»v.9,n.I,p6I-92.29» IISCHER M.J. Grammars with macro-like productions, Doctoral

31. Dissertation, Harvard Univ.,1968.

32. Автомата, алгорифмы, языке, 1982 ,с.31-41. 32» ГАВИЧЕВА А .В. 06 алгоритмической природе множества тавтологии и множества выполнимых формул логики высказываний. Дел .в ВИНИТИ 3 января 1983г., & 12 83 Дел.

33. ГАШЧЕВА А.В. Об одной мере сложности, дан контекстных языков. В кн.: Математическая логика »математике екая лингвистика и теория автоматов, 1983, СЛ2-21.

34. ГАШЧЕВА А.В. 0 некоторых свойствах множества тавтологиии множества выполнимых формул логики высказываний. Деп. в ВИНИТИ 26 апреля 1983 г., 182233 83 Дев.

35. ГАНИЧЕВА. А.В. 0 мере контекстна ста для множества тавтологий.- в печати.

36. ГАШЧЕВА А.В. 0 мере контекстное та для множества тавтологийпри упарном кодировании переменных. Детс. в

37. ВИНИТИ 29 августа IS83F. ,14729-83 Ден. 37* ГЛАДКИЙ А.В» формальные грамматики и языкм.М.:Наука,1973.

38. ЕШШ1Е F.C. On line Turing machine computations, JEEE

39. Trans, on Electronic Computers, EC-I5, 1966, п.I,p.35-44 /Русский перевод: Хенни Ф.К. Вшжсление на однсженточной машине; Тшринга с записьш. на ленте. В кн.: Проблемы математической логиш. М.: Мир Д ШО, с.223-248/.

40. ЗАРДЗИБЪ Я.М. Ложность распознавания симметрии на машине

41. Тьюринга, Проблема кибернетики, 1965, выи. 15» с.249-252.

42. A theorem on recursively enumerable sets. Absrt. of short comm. Int.Congress Math», 1962, Stockholm,p.II.

43. О функциях, элементарных no Скояему, Математические, заметки, 1Ш5» t.l7,JfeI, с Л 33-142.

44. Рудиментарное моделирование недетерминированных вычислений, Кибернетика, 1973, Л2, е.23-29.

45. Элементы математическом лютики и ее приложение к теории субрекурсивных алгоритмов. Л.: JUT,1981.

46. Примеры предикатов, невыразимых s-рудимен-тарными формулами;, Кибернетика, 1978 Д 2 , а.44-46.

47. Управление выводом в формальных грамматж-ках, Проблемы передачи информации, Ш1, т.?,вып.З, с.87-102.

48. Ш -g/zcuonmcuii txnd J\J- ^шл-гщ ал^ ? Ъг^сушг., <&ос. &tt, V.k, n.i, Д li-13. ^ob/naZ £cx.ficf,ita(^3 cuwi 'ъшлллйпъ icAeswe4i

49. ЯярсМ TR46-74, Ka/wrOLJid 1374.

50. Экономические интересы и их математическое моделирование,. Всесоюзный конкурс студенческих работ, 1976г. С работа отмечена дипломом П степени).сшьтсиг^ cutcL tAu/i tan.

51. Jotcnn-aß o^ Comp. (Xnd iydt. 'UizncM,1971,и.5, п.Ъ, р. 337-423.

52. Стоцкий Э.Д. Условные грамматики с рассеянным контекстом

53. ДАН, 1972, т.207, М, с.796-799.