Автоматная сложность вычисления формул тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Автоматная сложность вычисления формул в случае базиса, состоящего из одной операторной формулы длины

1.1 Постановка задачи.

1.2 Формулировка результатов и доказательство нижних оценок

1.3 Доказательство нижних оценок.

1.4 Доказательство пункта 3 из Теоремы 2.

2 Автоматная сложность вычисления формул в случае базиса, состоящего произвольного числа операторных формул длины

2.1 Вспомогательные утверждения

2.2 Случай базиса вида F — {((xaiy)a2z),((x(3iy)(32z)}.

2.3 Случай базиса вида F = {(xa1(ya2z)), (xfti(yf32z))}.

2.4 Автоматный случай. Доказательство части б) пункта 1 Леммы 10.

2.5 Случай базиса вида F = {((xaiy)a2z), (x0i(yP2z))}.

2.6 Формулировка общей теоремы.

3 Автоматная сложность вычисления формул в случае произвольного базиса, состоящего из операторных формул

3.1 Оценка числа базисов, для которых справедлива оценка SF(ti) х п.

3.2 Обобщенная конструкция.*

Проблема сложности автоматов является одной из наиболее актуальных задач теории автоматов. Сама теория автоматов ([11]), являющаяся разделом теории управляющих систем, изучает математические модели преобразователей дискретной информации, которые называются автоматами. Данный раздел математической науки возник в середине двадцатого века в связи с изучением конечных автоматов (в литературе также встречается термин последовательностные машины), как математических моделей нервных систем и вычислительных машин ([12]). Понятие конечного автомата впервые появилось в работах У. Мак-Каллока и У. Питта ([7]), С. К. К лини ([9]), А. Беркса и Дж. Райта ([8]). В дальнейшем класс объектов и проблематика теории автоматов заметно расширились, включив в себя некоторые понятия и задачи других разделов математики. Наиболее тесно теория автоматов связана с теорией алгоритмов ([10]), в частности с теорией абстрактных машин, поскольку автоматы можно рассматривать как их частный случай.

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

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

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

Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. При анализе поведений конечных автоматов часто возникает задача распознавания тех или иных свойств изучаемого автомата в процессе "эксперимента" с ним, т.е. подачи на вход автомата различных последовательностей и наблюдения за его реакцией. Известной до эксперимента является лишь неполная информация об автомате. Задача заключается в таком проведении эксперимента ([14]), чтобы необходимая информация возникала с наименьшими (в том или ином смысле) затратами. Интересные результаты в этой области получены Э. Ф. Муром [15] (оценка максимального простого условного установочного эксперимента), М. П. Василевским [16], [17](асимптотические оценки сложности экспериментов) и др.

Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием. К этой задаче примыкают проблемы, связанные с оценкой сложности автоматов, обладающих заданным поведением, а также с построением алгоритмов дающих в определенном смысле оптимальные автоматы. В частности, к данной категории относится задача минимизации автоматов, которая состоит в максимально возможном уменьшении значений параметров автоматов, приводящая к эквивалентным и в определенном смысле оптимальным автоматам (данная работа также относится к подобным задачам). При макроподходе минимизируют, как правило, число состояний автоматов, получая минимальные, или приведенные автоматы. Специфика отыскания приведенных автоматов связана с формой их задания и типа их поведения. Так, если в качестве поведения конечного автомата рассматривать систему ограниченно-детерминированных функций, реализуемых автоматом, то отыскание минимального конечного автомата эквивалентного данному эффективно осуществляется на основании теоремы Мура ([15]). При рассмотрении конечного автомата как акцептора ([9]), представляющего подмножеством выделенных состояний событие, описанное с помощью заданного регулярного выражения, минимальный автомат также строится эффективно ([18]).

Кроме того, применительно к классам исходных автоматов или автоматных отображений возникает проблема полноты. Задача о полноте имеет важное прикладное значение. На практике, прежде чем приступить к проектированию конкретной, часто весьма сложной, схемы, реализующей, например, какое-либо устройство управления, необходимо убедиться в том, что набор элементов, из которых будет вестись синтез этого устройства, является достаточным, т.е., например, что та ограниченно-детерминированная функция, которую требуется реализовать, действительная выразима через исходные "элементарные" функции. При этом условия, в которых предстоит "работать" синтезируемому устройству, могут накладывать различного рода ограничения на сложность (например, объем) реализации, надежность и т.д. В частности, в [2] доказывается существование конечных К-полных систем автоматов (полнота в смысле операций композиции и обратной связи). В [19] получен пример К-универсальной функции от двух переменных. Также в [2] показано, что любое Е-полное множество бесконечно (полнота в смысле операции композит). Также было доказано, что проблема полноты для класса автоматов в общем случае алгоритмически неразрешима ([20]).

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

Так, например, в случае такой модели вычислений как схема из функциональных элементов (СФЭ над базисом О), в качестве меры сложности вычисления функции / можно рассматривать минимальное число элементов базиса О, достаточное для реализации / СФЭ над

Еще одним примером подобной меры (в алгебре логики) может служить длина формулы, реализующей / над некоторым базисом П. Проблема оценки длины формулы, реализующей ту или иную функцию / над фиксированным базисом П, широко изучалась многими математиками. Из наиболее значительных результатов в этой области стоит выделить работы О.Б. Лупанова, которым была получена асимптотически точная оценка длины формул при реализации функций в произвольном базисе ([21], [22]). Так, в случае базиса V, —асимптотическая точная оценка (для функций от п переменных) имеет вид (1 + б)2и/1о§2п (в случае произвольного полного базиса эта оценка изменяется на мультипликативную константу). Так же О.Б. Лупанов ([23]) получил асимптотическую точную оценку сложности контактных схем для те-местных булевских функций - (2п/те)(1 + б).

Важные методы получения оценок длин формул были предложены В.М. Храпченко ([24]) для базиса {&, V, ->}, Э.И. Нечипоруком ([25]) для произвольного базиса, для случая монотонных симметрических функций Р. Е. Кричевским ([26]), Ж. Анселем ([27]) (здесь также следует упомянуть работы Дж. Фридмана [29], С. А. Ложкина, А. А. Семенова [28]).

Если же в качестве модели вычислений рассматривать машины Тьюринга, то в качестве меры сложности можно рассматривать длину самой короткой программы для вычисления / на данной машине Тьюринга ([30]). Другой подход к данной проблеме заключается в оценке сложности машины Тьюринга, вычисляющей функцию /, через число ее внутренних состояний ([31]). Таким же образом можно оценивать сложность конечных автоматов.

Так, В.А. Кузьмин ([31]) показал, что любую функцию алгебры логики от п переменных можно реализовать автоматом со сложностью ~ а(те)2п/п, а(п) £ [1,2]. Этот результат основан на конструктивном подходе для синтеза контактных схем, предложенный Г.Н. Поваровым ([32]). Немного позже было показано [33], что сложность реализации булевых функций автоматами в значительной степени менее выгодна нежели аналогичная конструкция в классе машин Тьюринга.

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

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

Непосредственно задача, которая рассматривается в данной работе исторически появилась относительно недавно (одной из первых публикацией на эту тему стала работа А. Е. Андреева и А. А. Часовских, опубликованная в 1996 г. [3]) и относится к классу сложностных оценок в теории автоматов.

Общая формулировка задачи, о которой пойдет, может быть описана следующим образом. Зафиксируем некоторое конечное множество Р (называемое базисом) формул в операторной форме над множеством всех двуместных булевских операций. При этом в рамках данной задачи мы будем дополнительно считать, что заданная запись каждой формулы из базисного множества Р предполагает не более чем однократное вхождение символа одной и той же переменной. Далее будем строить над этим множеством термы в смысле суперпозиции [1]. Однако, мы не будем предполагать в термах переменных, а только константы 0 и 1. Совокупность этих выражений обозначим через Ф(-Р), элементы этого множества (далее просто термы) и будут являться объектами нашего рассмотрения.

Таким образом элементы множества Ф(^) представляют собой слова над некоторым конкретным алфавитом V. В частности, если все формулы из Р заданы в операторной форме, то этот алфавит будет иметь вид К>р = {аъ •••) ак, (,); 0,1}, где символы а\,.,ак есть значки булевских операторов (другой вариант данной задачи возникает, если все формулы из Р заданы в префиксной форме, т.е. в виде /(х,у), тогда алфавит будет иметь вид Ург = {/1,., (,), 0,1}, где символы /1,., Д есть значки функциональных символов).

Пусть теперь у нас есть элемент ф 6 Ф(Р), число символов соответствующего алфавита V, содержащихся в слове ф назовем его длиной ф и обозначим через \ф\.

Множество термов над Р, чья длина не превышает некоторого константу п обозначим через Фп(Р) = {Ф £ < п}. Произвольный терм из множества Фп(-^) подается на вход конечного инициального автомата А без выхода [2], А = (V, который должен вычислить значение функции, реализуемой данным термом (здесь"символами V, о обозначены входной алфавит, алфавит состояний, функция переходов и начальное состояние соответственно). Под термином 'вычислить' мы подразумеваем следующее: автомат А вычисляет Фn(F)

3q°, q1 € Q : Va e Ф»(П £(«>, «) = { " " ?

Здесь под метаобозначением a = const подразумевается тот факт, что значение функции, реализуемой термом а равняется указанной константе.

Требуется оценить минимально возможное число состояний автомата А вычисляющего $n(F) как функцию параметров F и п. Данную оценку будем проводить при помощи величины Sp{n) = min {log2\Q\ : А вычисляет ФП(.Р)}. В связи с тем, что данная работа является одной из первых в этой обсласти, то оценка сложности производилась по порядку.

Поставленная таким образом задача корректна в том смысле, что, если на вход изучаемого автомата А подается терм из множества Фп(Г), то автомат вычисляет (в указанном смысле) значение функции, реализуемой данным термом. Напомним, что согласно сделанным предположениям запись каждой формулы из базиса F предполагает не более чем однократное вхождение символа одной и той же переменной. Различные вариации этой задачи могут появляться, если мы будем рассматривать разные формы записи формул из множества F (операторную, префиксную, польскую), а также варьировать число длину этих формул.

Как уже было отмечено выше одним из первых результатов в этой области стала работа [3], в которой рассматривались базисы F, которые могли состоять из операторных формул длины не более чем 5 (т.е. вида (ж о у), где о — значок бинарной булевской операции), а также префиксной и суффиксной форм отрицания. В этом случае была получена Теорема, которая позволяет произвести определить порядок роста последовательности 5jr(n) для любого множества F указанного вида (см. Теорему 1). При этом оказалось, что в зависимости от вида базиса F величина может принимать значения (по порядку) 1, log га, п.

Естественным продолжением данной работы стало исследование базисов F, в которые могли входить формулы большей длины. Первым шагом в этом направлении стало изучение базисов, состоящих из операторных формул длины 9 (т.е. вида ((жоy)*z), (xo(y*z)), где о, * — значки бинарных булевских операций). В данном случае был получен результат ([5]) аналогичный [3]. Однако оказалось, что число базисов для которых справедлива оценка Spin) х п значительно больше (в процентном отношении) нежели чем в случае рассмотреном А.Е. Андреевым и A.A. Часовских . Последнее обстоятельство дало возможность выдвинуть гипотезу о том, что в общем случае для почти всех базисов (состоящих из операторных формул) справедлива данная оценка. Это предположение подтвердилось: оказалось, что при увеличении максимально допустимой длины формул, входящих в базис F, отношение числа базисов, для которых справедлива указанная оценка, к общему числу допустимых базисов стремится к 1.

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

При этом при изучении данной задачи встал вопрос о возможности построения базиса Р, для которого функция принимала бы значение (по порядку) отличное от 1, log га, п. Подобный примеры были построены для случая счетнозначной логики, где был сконструированы базисы, для которых справедливы оценки 5f(n) х log log га и 5V(n) х log2 п.

Из дополнений к данной работе стоит выделить рассмотрение случая базисов F, состоящих из формул в префиксном виде длины не более чем 6 ([4]), для которого был получен результат аналогичный операторному случаю. Однако здесь выяснилось, что в смысле рассматриваемых сложностных оценок префиксная запись оказывается заметно хуже операторной. В рамках рассматриваемой задачи также был рассмотрен вопрос о связи различных замкнутых классов Поста (см. [1]) и сложностью автоматов, вычисляющих значения функций, реализованных формулами.

1. Гаврилов Г. П., Кудрявцев В. Б., Яблонский С. В. Функции алгебры логики и классы Поста. - М.: Наука, 1966

2. Кудрявцев В. В., Алешин С. В., Подколзин А. С., Введение в теорию автоматов М.: Наука, 1985

3. Андреев А.Е., Часовских A.A. Сложность автоматов, вычисляющих значения формул. Вестник МГУ. Серия математика и механика. N 4, 1996.

4. Кудрин А. А. Сложность автоматов, вычисляющих значения функций, заданных в префиксном виде. Вестник МГУ. Серия математика и механика. N 1, 1998.

5. Кудрин А. А. Сложность автоматов, вычисляющих значения формул над базисом, состоящим из одной булевской функции (записанной в операторном виде). Интеллектуальные системы, М., 1999, Т. 4, вып. 1-2, с. 285-298

6. Кудрин A.A. Сложность автоматов, вычисляющих значения функций, реализованных термами // Интеллектуальные системы. М.: 1999. Т. 4. Вып. 3-4.с. 271-284

7. Мак-Каллок У., Питтс В., в сб.: Автоматы, М., 1956, с 362-384

8. Беркс А., Райт Д. Теория логических сетей. М.: ИЛ, Кибернетический сборник, 1962, 4, с. 33-57

9. К лини С. К., Представление событий в нервных сетях и конечных автоматах. В кн.: Автоматы. - М.: ИЛ, 1956, с 15-67

10. Лупанов О.Б. Об одном методе синтеза схем Известия высших учебных заведений. Радиофизика. - 1958. -Т.1, №1. - С.120-140.

11. Храпченко В.М. Об одном методе получения нижних оценок сложности П-схем. Математические заметки. - 1971. -Т.10, №1. - С.83-92.

12. Нечипорук Э.И. Об одной булевской функции. Доклады АН СССР.- 1966. -Т.169, №4. С.765-766.

13. Кричевский Р. Е. Сложность контактных схем, реализующих одну функцию алгебры логики. Доклады АН СССР. - 1963. -Т.151, №4.- С.803-806.

14. Ансель Ж. Минимальное число замыкающих контактов, достаточное для реализации одной симметрической булевой функции п переменных. Кибернетический сборник. Новая серия. Вып. 5. - М.: Мир, 1968. - С.53-57.

15. Ложкин С.А., Семенов A.A. Об одном методе сжатия информации и о сложности реализации монотонных симметрических функций.- Известия высших учебных заведений. Математика. 1988. - №7. -■ С.44-52.

16. Friedman J. Costructing 0(n log n) size monotone formulae for the k-th elementary symmetric polynomial of n Boolean variables. SIAM J.Comput. - 1986. - V.15,№3. - P.641-654.

17. Сэвидж Дж. Э. Сложность вычислений. M.: Факториал, 1998.

18. Кузьмин В. А. Реализация функций алгебры логики автоматами, нормальными алгорифмами и машинами Тьюринга. Проблемы кибернетики, вып. 13. - 1963. - С.75-96.

19. Поваров Г.Н. Математико-логическое исследование синтеза контактных схем с одним входом и к выходами. В сб. "Логические исследования", Ан СССР, 1959.

20. Брейтбарт Ю. Я. О сравнении сложности реализаций булевых функций автоматами и машинами Тьюринга. ДАН СССР, 1968, т. 180, №5