Автоматная сложность вычисления формул

Содержание
Введение 4
1 Автоматная сложность вычисления формул и случае базиса, состоящего из одной операторной формулы длины
9 11
1.1 Постановка задачи.......................................... 11
1.2 Формулировка результатов и доказательство нижних оценок 13
1.3 Доказательство нижних оценок............................... 19
1.4 Доказательство пункта 3 из Теоремы 2........................23
2 Автоматная сложность вычисления формул и случае базиса, состоящего произвольного числа операторных формул длины 9 26
2.1 Вспомогательные утверждения ............................... 26
2.2 Случай базиса вида Г = {((ха|у)а?г),((т^|у)Дгг)}............30
2.3 Случай базиса вида/■' = {(то’|(усг2;)),(хД(у/?2^))}.........33
2.4 Автоматный случай. Доказательство части б) пункта 1 Леммы 10........................................................ 36
2.5 Случай базиса вида Г = {((ха1у)о2г’),(х^1(у^2г))}...........44
2.6 Формулировка общей теоремы..................................47
3 Автоматная сложность вычисления формул в случае произвольного базиса, состоящего из операторных формул 48
3.1 Опенка числа базисов, для которых справедлива оценка 5/г(п) х п...................................................... 48
3.2 Обобщенная конструкция......................................55
2
4 Случай префиксной записи формул 59
4-1 Определения и формулировки результатов...................59
4.2 Случай базиса мощности 1.................................62
4.3 Случай базиса мощности 2.................................74
4.4 Пример базисов Г, для которых справедливы оценки 5НП) ~
1ой1одп и 5г(п) х 1о§2п..................................81
4.5 О связи замкнутых классов Поста и сложности автома-
татов, вычисляющих значения функций, реализованных формулами................................................93
г
3
Введение
Проблема сложности автоматов является одной из наиболее актуальных задач теории автоматов. Сама теория автоматов ([11]), являющаяся разделом теории управляющих систем, изучает математические модели преобразователей дискретной информации, которые называются автоматами. Данный раздел математической науки возник в середине двадцатого века в связи с изучением конечных автоматов (в литературе также встречается термин последовательностные машины), как математических моделей нервных систем и вычислительных машин ([12]). Понятие конечного автомата впервые появилось в работах У. Мак-Каллока и У. Питта ([7]), С. К. Клшш ([9]), А. Беркса и Дж. Райта ([8]). В дальнейшем класс объектов и проблематика теории автоматов заметно расширились, включив в себя некоторые понятия и задачи других разделов математики. Наиболее тесно теория автоматов связана с теорией алгоритмов ([10]), в частности с теорией абстрактных машин, поскольку автоматы можно рассматривать как их частный случай.
Характерной особенностью данной конструкции является ее дискретность, а также конечность областей значений ее параметров, что собственно а приводит к понятию конечного автомата. При этом внешние воздействия, реакции и состояния рассматриваются как буквы трех алфавитов, называемых, соответственно, входным алфавитом, выходным алфавитом и алфавитом состояний. Тогда законы их взаимодействия могут быть заданы двумя функциями - переходов и выходов, отображающими пары "состояние - входная буква" в состояния и выходные буквы соответственно. В каждый из моментов дискретного времени устройство, находящееся в определенном состоянии, воспринимает входной сигнал - букву входного алфавита, выдает выходной сигнал - букву выходного алфавита, определясмую функцией выходов, и переходит в новое состояние, определяемое функцией переходов.
Существуют различные подходы к определению конечного автомата ([13]). При макроподходе, т.е. когда представляет интерес лишь внешнее поведение устройств, определение лого понятие может быть дано в виде совокупности функций, либо з виде конечного ориентированного графа, либо в алгебраической форме в виде конечной алгебры с унарными операциями ((2]). При микроподходе конечный автомат задается множеством элементов и схемой их соединения, т.е. в этом случае кроме функционирования описывается и строение автомата, в связи с чем это
4
понятие обычно называют структурным, а сами конечные автоматы -структурными автоматами, или автоматными сетями.
Большинство задач теории автоматов схожи с основными видами проблем обшей теории управляющих систем. К ним относятся задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и др.
Задача анализа состоит в том, чтобы по заданному автомату описать ею поведение или по неполным данных! об автомате и его функционированию установить те или иные его свойства. При анализе поведений конечных автоматов часто вознихаст задача распознавания тех или иных свойств изучаемого автомата в процессе * эксперимента“ с ним, т.е. подачи на вход автомата различных последовательностей и наблюдения за его реакцией. Известной до эксперимента является лишь неполная информация об автомате. Задача заключается в гаком проведении эксперимента ([14]), чтобы необходимая информация возникала с наименьшими (в том или ином смысле) затратами. Интересные результаты и этой области получены Э. Ф Муром (15) (оценка максимального прос того условного установочного эксперимента), М. П. Василевским [16], (17](асимптотические оценки сложности экспериментов) и др.
Задача синтеза автоматов состоит в построении автохеата с наперед заданным поведепием или функционированием. 1< этой задаче примыкают проблемы, связанные с оценкой сложности аато?^атов, обладающих заданным поведением, а также с построением алгоритмов дающих в определенном смысле оптимальные автоматы. В частности, к данной категории относится задача минимизации автоматов, которая состоит в максимально возможном уменьшении значений параметров автоматов, приводящая к эквивалентным и в определенном смысле оптимальным автоматам (данная работа также относится к подобным задачам). При макроподходе минимизируют, как правило, число состояний автоматов. получая минимальные, или приведенные автоматы. Специфика отыскания приведенных автоматов связана с формой их задания и типа их поведения. Так, если в качестве поведения конечного автомата рассматривать систему ограличенно-детермянвровалных функций, реализуемых автоматом, то отыскание минимального конечного автомата эквивалентного данному эффективно осуществляется на основании теоремы Мура {[15]). При рассмотрении конечного автомата как акцептора (|9])? представляющего подмножеством выделенных состояний событие,
5
описанное с помощью заданного регулярного выражения, минимальный автомат также строится эффективно ([18]).
Кроме того, применительно к классам исходных автоматов или автоматных отображений возникает проблема полноты. Задача о полноте имеет важное прикладное значение. На практике, прежде чем приступить к проектированию конкретной, часто весьма сложной, схемы, реализующей, например, какое-либо устройство управления, необходимо убедиться в том, что набор элементов* из которых будет вестись синтез этого устройства, является достаточным, т.е., например, что та ограпичеппо-детермипиропаипая функция, которую требуется реализовать. действительная выразима через исходные "элементарные* функции. При этом условия, в которых предстоит "работать” синтезируемому устройству, могут накладывать различного рода ограничения на сложность (например, объем) реализации, надежность и т.д. В частности, в (2] доказывается существование конечных К-подиых систем автоматов (полнота в смысле операций композиции и обратной связи). В [19] получен пример К-универсальной функции от двух переменных. Также в (2) показано, что любое Е-полное множество бесконечно (полнота в смысле операции композит). Также было доказано, что проблема полноты для класса автоматов в общем случае алгоритмически неразрешима ([20]).
Проблема сложности вычислений является одной из наиболее актуальных задач дискретной математики. Для различных моделей вычислений используются самые разнообразные методы оценки их сложности.
Так, например, в случае такой модели вычислений как схема из функциональных элементов (СФЭ над базисом П), в качестве меры сложности вычисления функции / можно рассматривать минимальное число элементов базиса 0. достаточное для реализации / СФЭ над П.
Еще одним примером подобной меры (в алгебре логики) может служить длина формулы, реализующей / над некоторым базисом П. Проблема оценки длины формулы, реализующей ту или иную функцию / над фиксированным базисом П, широко изучалась многими математиками. Из наиболее значительных результатов в этой области стоит выделить работы О. В. Лупаяова, которым была получена асимптотически точная оценка длины формул при реализации функций в произвольном базисе ((21), (22)). Так. в случае базиса {&,Уо} асимптотическая точная оценка (для функций от п переменных) имеет вид (1 + с)2п/1ой2;* (в случае произвольного полного базиса эта оценка изменяется на муль-
б
ти пли кати иную константу). Так же О.В. Лупанов ([23]) получил асимптотическую точную оценку сложности контактных схем ДЛЯ »-местных булевских функций - (2"/п)(1 + е).
Важные методы получения оценок длин формул были предложены В.М. Хралченко ((24)) дня базиса {&. V, -ч}, Э-И. Нечяпоруком ([25]) для произвольного базиса, для случая монотонных симметрических функций Р. Е. Кричевским ([26]), Ж. Апселем ([27]) (здесь также следует упомянуть работы Дж. Фридмана (29', С. А. Ложкина, А. А. Семенова [28]).
Если же ь качестве модели вычислений расе мат р ивать машины Тьюринга, то в качестве меры сложности можно рассматривать длину самой короткой программы для вычисления / на дайной машине Тьюринга ((30)). Другой подход к данной проблеме заключается в оценке сложности машины Тьюринга, вычисляющей функцию /, через число се внутренних состояний ([31]). Таким же образом можно оценивать сложность конечных автоматов.
Так, В.А. Кузьмин ([31]) показал, что любую функцию алгебры логики от п переменных можно реализовать автоматом со сложностью ~ а(п)2ч/п,о(») 6 [1,2]. Этот результат основан на конструктивном подходе для синтеза контактных схем, предложенный Г.Н. Поваровым ([32]). Немного позже было показано [33]. что сложность реализации булевых функций автоматами в значительной степени менее выгодна нежели аналогичная конструкция п классе машин Тьюринга.
Отличие задачи, рассмотренной в данной работе от предыдущей заключается в том. что в данном случае на вход конечного автомата подается суперпозиция исходных формул, реализующих некоторые функции алгебры логики, что естественно ведет к увеличению его сложности.
Проблема, которая будет рассмотрена в данной работе связана со сложнсстными оценками а теории автоматов. В данной задаче продолжается изучение перечислительных свойств конечных автоматов. Подобные задачи возникают, когда входная информация считывается некоторым анализатором, вообще говоря, без запоминания и без возможности ее полного восстановления в дальнейшем, но при необходимости принятия решения этим анализатором. Простейшими примерами подобных анализаторов могут служить: функция подсчета скобочного баланса в компиляторе компьютерных программ (которые, как правило, имеют линейную относительно длины программы сложность и ограни-