Содержание к диссертации
Введение
Глава 1. Сложность условного установочного эксперимента для различных классов автоматов 21
1. Введение 21
2, Основные определения и результаты 21
3. Вспомогательные утверждения 23
4. Доказательство теорем 1 и 2 38
5. Доказательство теорем 3 и 4 41
6. Доказательство теорем 5 и б 47
7. Связь длины установочного эксперимента с разбиениями Rk 50
Глава 2. Сложность установочного эксперимента для автоматов без выхода 53
1. Введение 53
2, Основные понятия и результаты 53
3. Доказательство теорем 1,2 и 3 54
4. Доказательство теоремы 4 58
5. Вспомогательные определения и леммы .60
6. Доказательство теоремы 5 66
7. Случай автоматов над термами. Вспомогательные определения и леммы 70
8. Доказательство теоремы о времени склейки г состояний автомата для почти всех автоматов над термами 74
9. Некоторые оценки для времени склейки г состояний в автоматах над термами 77
Глава 3. Соотношение сложностей условного и безусловного экспериментов 79
1. Введение 79
2. Основные определения и формулировка результатов 79
3. Доказательство теоремы 1 80
4. Доказательство теоремы 2 81
Глава 4. Установочный эксперимент для частично-определённых автоматов 87
1, Введение 87
2. Основные определения и результаты 87
3. Понятия и результаты 88
4. Доказательство теорем 1 и 2 91
5. Оценки длины условного установочного эксперимента для частичных автоматов 97
Глава 5. Установочные эксперименты для автоматов с изменяемой логикой поведения 99
1. Введение 99
2. Основные определения и результаты 100
3. Понятия и результаты. 102
4. Связи степени отличимости автомата с длиной установочного эксперимента 105
5. Теорема об условной степени отличимости 107
6. Доказательство теоремы 1
7. Доказательство теоремы 2
8. Доказательство теорем 3 и 4 113
Заключение 115
Список литературы 117
- Связь длины установочного эксперимента с разбиениями Rk
- Случай автоматов над термами. Вспомогательные определения и леммы
- Оценки длины условного установочного эксперимента для частичных автоматов
- Связи степени отличимости автомата с длиной установочного эксперимента
Введение к работе
Актуальность темы. Настоящая работа посвящена исследованию свойств установочного эксперимента с автоматами. Если Я. = (A, Q, В, (р, ф)— конечный автомат, где А — входной алфавит, В —выходной алфавит, Q — множество состояний, tp, ф функции переходов и выходов, Тр : Q х А* —* Q, ф : Q Я. А* —* В*,- естественные продолжения функций ^р и ф на слова из алфавита А*, то простым условным установочным экспериментом для автомата Я называется ориентированное от корня дерево, вершинам которого приписаны подмножества множества Q и слова входного алфавита, а ребрам приписаны слова в выходном алфавите автомата, причем таким образом, что корню приписано все множество состояний, а листьям одноэлементные подмножества и для каждой неконцевой вершины г; дерева выполняется следующее условие : если av- слово, приписанное вершине v, то
-
для каждой вершины q Є Qv, если /?, = ф^,ау), то найдется ребро е = iyw), выходящее из вершины v и оканчивающееся в вершине w такое, что Рч = ре и Tp{q, av) Є Qw, где Qv и Qw- подмножества состояний, приписанные вершинам v и w соответственно, /?е— слово, приписанное ребру е;
-
если е = (vw) - ребро, выходящее из вершины v и оканчивающееся в вершине w, то Qw ф 0 и для каждого состояния q1 Є Qw существует состояние q Є Qv такое, что lp(q, а„) = q11.
Максимальная из сумм длин слов, приписанных вершинам ветвей описанного дерева, представляющего эксперимент, ведущих от корня к листу называется длиной эксперимента. Минимальную из длин простых установочных экспериментов для автомата Я обозначим /(). Если для автомата Я не существует простого условного установочного эксперимента, то полагаем L(2t) = 0. Известно 1, что для приведенных автоматов такой эксперимент существует всегда.
Простым безусловным установочным экспериментом для автомата Я называется слово а є А*, такое, что для любых двух состояний автомата 1) Є Q выполнено: если ^(1,^) = ф^г,а), то v{q\,a) = ip(q2,cx). Слово а называется установочным для Я. Кратчайшую из длин установочных слов для автомата Я обозначим и(Я). Если для автомата Я не существует ни одного установочного эксперимента, то полагаем i„(2t) = 0. Известно2, что
1 В.Б.Кудрявцев, С.В.Алешин, А.С.Подколзин. Введение в теорию автоматов. Москва. "Наука". 1985.
*Htbbard Т.Н Least upper bounds on minimal terminal state experiments for two classes of sequential machines, J. Assoc. Сотр. Mach. 8, №4(1961), 601-612[русский перевод см. "Кибернетический сборник (новая серия), вып. 2(1966), 7-23 ]
(
если автомат приведен, то он имеет по крайней мере одну установочную последовательность.
Если К - некоторый класс автоматов, то обозначаем 1(К) = тпах1(%),
если такой максимум существует, в противном случае полагаем I(К) = со. Аналогично, если К - некоторый класс автоматов, то обозначаем lu(K) = maxlu(%.), если такой максимум существует, в противном случае полагаем
2 Л
ЦК) = со.
Остаточной степени отличимости автомата й называется минимальное натуральное число h со свойством,что для любых двух состояний автомата qi, ф автомата & выполняется одно из условий:
-
существует слово а такое, что 1(a) ^ ft и ip(qi, а) Ф ф(д2, а);
-
существует слово а такое, что 1(a) ^ h и 7p(q\,a) = ^5(> <*)
Теория экспериментов с автоматами является достаточно хорошо развитой ветвью теории автоматов. Однако в последнее время, в связи с необходимостью верифицировать интернет-протоколы, появилось большое число работ, посвященных теории экспериментов с автоматами, например 3 4. В обзорной работе 3 приведены и обобщены практически все основные результаты теории экспериментов на сегодняшний день. В основном, авторы указанных работ рассматривают диагностические и тестовые эксперименты, то есть эксперименты, позволяющие либо полностью предсказать дальнейшее поведение автомата, либо отличить автомат от предъявляемого эталона. В обоих случаях установочный эксперимент играет роль строительного блока. Рассмотрим,например, тестовый эксперимент. Задача тестового эксперимента состоит в том, чтобы по предъявляемому автомату и некоторому эталонному автомата сказать, эквиваленты ли по поведению эти автоматы. Поскольку мы не знаем, в каком состоянии находится предъявляемый автомат, то сначала необходимо построить установочный эксперимент для эталона и применить его к тестируемому автомату. Если уже на этом этапе выявятся отличия поведения эталона и тестового автомата, то мы сможем заключить, что тестовый автомат и эталон неэквивалентны, в противном случае, мы проведем установочный эксперимент до конца и сможем теперь сформулировать гипотезу относительно текущего состояния тестового автомата. Дальше начинает работу непосредственно тестовый эксперимент. Аналогичная схема применяется и при построении
3D.La, U Yannakoku Principles and methods of testing finite state machines. Proc of the IEEE, vol 84, 1090-1123, 1996.
*R.L. Rhtst R E Shaptre Inference of finite state automata using homing sequences. Proc 21st Annual ACM Symp. on Theory of Computing, 411-420, 1989
диагностических экспериментов. На самом деле в работе5,при построении в некотором смысле алгебраической теории экспериментов с автоматами, показывается, что в определенном алгебраическом смысле установочные эксперименты, как "строительные блоки", необходимы при построении тестовых и диагностических экспериментов. Таким образом задача построения оптимизации установочного эксперимента является необходимой при построении и оптимизации диагностических и тестовых экспериментов.
Понятие установочного эксперимента условного и безусловного было введено Муром в работе 6. Там же доказывается теорема о том, что если Кп - класс автоматов с не более, чем п состояниями, то 1(Кп) < я'"2~". В работе 7 Хиббард доказал, что для этого класса на самом деле имеет место равенство l(Kn) = 2
Однако в примере Хиббарда, на котором достигается оценка п'"~ ' использовался входной алфавит с в — 1 символами и оставался открытым вопрос о том, какова оценка для длины установочного эксперимента в случае, если ограничить рост входного алфавита. В первой главе работы исследуется вопрос о зависимости длины условного установочного эксперимента от длины входного алфавита. Установлена возможность понижения оценки Мура-Хиббарда уже при п — 9 входных символах. Показано также, что порядок этой оценки сохраняется вплоть до двухбуквенного входного алфавита.Отметим, что в работе 8 Карацуба рассматривал задачу о получении оценок для функции 1(К'п), где через К'п обозначен класс приведенных автоматов Мура с п состояниями. Он показал, что 1{К'п) = ("~ Дп~ ) + і. В примере автомата, на котором достигается нижняя оценка, используется входной алфавит из п — 2 символов. В главе 1 показывается, что квадратичный порядок из оценки Карацубы сохраняется вплоть до двухбуквенного входного алфавита, в то же время с помощью развитой в главе 1 техники можно установить возможность понижения верхней оценки в классе автоматов Мура с менее, чем с п — 9 входными символами.
С задачей построения установочного эксперимента тесно связана задача синхронизации9. Эту задачу можно рассматривать как установочную в
5 Я. С. Грунский, В А Козловский, Г.Г. Пономаренко Представления конечных автоматов. Киев, Наукова думка 1990.
6Moore E.F. Gedanken-experiments on sequential machines, Automata Studies, 1956, 129-153[руссхни перевод см. "Автоматы"(сб. статей), ИЛ, 19566 179-210)
7Hibbard Т Н. Least upper bounds on minimal terminal state experiments for two classes of sequential machines, J. Assoc Comp Mach. 8, №4(1961), 601-612[русскиЯ перевод см. "Кибернетический сборник"(новая серия), вып. 2(1966), 7-23.]
8Карацуба А А. Решение одной задачи из теории конечных автоматов, УМН 15, №3 (1960), 157-159.
9D.Lee, М. Yanr.akakis Principles and methods of testing finite state machines. Proc of the IEEE, vol 84,
классе автоматов без выходов. Кроме этого понятно, что и в случае автоматов с выходами возможность склеивать состояния в процессе эксперимента оказывает существенное влияние на структуру и сложность эксперимента.
Во второй главе исследуются вопросы о нахождении длины кратчайшей синхронизирующей последовательности для различных подмножеств состояний автоматов в различных классах. Рассматриваются две основные задачи:
-
получение оценок шенноновского типа для длины синхронизирующей последовательности;
-
получение средней длины синхронизирующего слова для почти всех автоматов.
При фиксированном г получен порядок для длины кратчайшего синхронизирующего слова для г— элементных подмножеств состояний в следующих двух классах автоматов : классе всех автоматов с п состояниями и классе автоматов с п состояниями, имеющих синхронизирующее слово сразу для всех состояний. Получена асимптотика длины кратчайшего синхронизирующего слова для г— элементных подмножеств состояний для почти всех автоматов с п состояниями при г < log2log2 log2n и п —* оо.
В работе10 Саломаа рассмотрел задачу синхронизации в классе автоматов над термами11. В работе рассмотрена задача о средней высоте синхронизирующего терма в автоматах над термами. Получена асимптотика длины кратчайшего синхронизирующего терма для г— элементных подмножеств состояний для почти всех автоматов над термами с п состояниями при г < log2 log2 log2 п и n -+ CO.
Отметим, что подобные задачи "усреднения"в дискретной математике рассматривались различными авторами, например в 12 рассматривается задача поиска усредненного значения веса автомата, в 13 рассматривается задача нахождения усредненного значения степени отличимости автомата, однако используемый в настоящей работе подход к решению задачи синхронизации имеет существенные отличия от походов указанных работ, продиктованные спецификой рассматриваемой задачи.
Понятно, что в общем случае длина условного установочного
1090-1123, 1996.
10 A. Salomon Synchronization of finite state automata. Contribution to an old problem. Turku Center For Computer Science Technical Report №365(2000).
11В Б.Кудрявцев, С.В.Алешин, А С Подколзин. Введение в теорию автоматов. Москва. "Наука". 1985.
пБардзинъ ЯМ. О расшифровке автоматов, сб."Проблемы кибернетики", вып. 21, "Наука", 1969, 103-114.
гз Коршунов А Д О степени различимости конечных автоматов, Дискретный анализ, вып 10( 1967), 39-57.
эксперимента меньше длины безусловного для того же автомата. В третьей главе рассмотрена задача о соотношении длин условного и безусловного установочных экспериментов. Получен порядок для максимального значения отношения длин безусловного и условного установочного экспериментов. Получен порядок для значения отношения длин безусловного и условного установочного экспериментов для почти всех автоматов с п состояниями при п —> со.
В четвертой главе рассматривается задача определения длины установочного эксперимента для частичных автоматов. Такая постановка задачи может возникать например в случаях, когда некоторые переходы автомата являются запрещёнными в том смысле, что переход по ним может привести к неисправностям автомата. В этом случае в процессе проведения эксперимента допускается подавать лишь слова, которые не приводят к повреждениям автомата. При —> 0 получена асимптотика для длины условного установочного эксперимента для г— элементных подмножеств состояний частичных автоматов, где п—число состояний автомата. При jj < i(l — ),0 < є < 1 получен порядок длины условного установочного эксперимента для г— элементных подмножеств состояний частичных автоматов. Получена верхняя оценка вида Clog|n для остаточной степени отличимости равномерно для почти всех частичных автоматов с п состояниями и к выходными символами при п —> оо. Указанная оценка обобщает оценку сверху Я. М. Бардзиня вида С log* п для степени отличимости равномерно для почти всех обыкновенных автоматов.14
В пятой главе рассматривается задача о нахождении оценок длины условного установочного эксперимента шенноновского типа при возможности произвольно перенаправлять р стрелок в диаграмме переходов автомата, либо произвольно менять значение функции выходов в р точках. Такая постановка задача может возникать в случае, когда исследуемый автомат требуется упростить в смысле изменения его логики поведения таким образом, чтобы установочный эксперимент имел максимально простую структуру. Получены верхние и нижние оценки для длины условного установочного эксперимента при возможности произвольно изменить функцию выходов в р точках, либо поменять значение функции переходов в р точках. Отметим, что подобные вопросы о зависимости длины контрольного(тестового) эксперимента от локальных преобразований диаграммы переходов автомата рассматривались в работе15. Однако в этой работе рассматривались лишь преобразования, не выводящие автомат за
1*Б А Трахтенброт, ЯМ Бардзинь Конечные автоматы(Поведение н Синтез). Москва. "Наука". 1970.
15Козловский В. А. О распознавании автомата относительно локально порожденного класса. Докл. АН СССР - 1981. - 258, 5. - С. 1047 - 1049.
рамки так называемого локально-порожденного класса , то есть новые переходы могли осуществляться лишь в состояния, смежные с исходным состоянием на старой диаграмме переходов. Возникшая в настоящей работе техника для решения подобных задач принципиально отличается от техники, используемой в 14 .
Цель работы. Целью работы является изучение свойств установочного эксперимента с автоматами, постановка и решение новых задач, связанных с установочными экспериментами, а также изучение некоторых задач, связанных с установочным экспериментом, таких как задача о синхронизирующем слове.
Методы исследования. В диссертации используются методы дискретной математики и математической кибернетики.
Научная новизна. Все результаты работы являются новыми, основные результаты состоят в следующем:
-
Показано, что при п > 9 классическая оценка сложности условного установочного эксперимента п'"2~-' может быть понижена в классе автоматов с менее, чем п — 8 входными символами, где п— число состояний автомата. В то же время показано, что квадратичный порядок указанной оценки сохраняется при любом входном алфавите.
-
Получена асимптотика длины кратчайшего синхронизирующего слова для г— элементных подмножеств состояний для почти всех автоматов с п состояниями при г < log2log2log2пип-юо.
3. Получен порядок для максимального значения отношения длин
безусловного и условного установочного экспериментов. Получен порядок
для значения отношения длин безусловного и условного установочного
экспериментов для почти всех автоматов с п состояниями при п —* со.
4. При jj — 0 получена асимптотика для длины условного установочного
эксперимента для г— элементных подмножеств состояний частичных
автоматов, где п—число состояний автомата. При Jj < ^(1 — ), 0 < е <
1 получен порядок длины условного установочного эксперимента для г—
элементных подмножеств состояний частичных автоматов.
5. Получены верхние и нижние оценки для длины условного
установочного эксперимента при возможности произвольно изменить
функцию выходов в р точках, либо поменять значение функции переходов
в р точках.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть полезны специалистам, занимающимся проблематикой экспериментов с автоматами таких научных учреждений, как Московский Государственный Университет им. М. В. Ломоносова, Институт прикладной математики им. М. В. Келдыша
РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С.Л. Соболева СО РАН, Нижегородского государственного университета им. М. В. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственного университета.
Апробация работы.
Результаты работы докладывались и обсуждались на следующих семинарах механико-матеметического факультета МГУ: семинар "Теория автоматов", под рук. академика В,Б. Кудрявцева( неоднократно), семинар "Элементы кибернетики "под руководством профессора, доктора ф.м. наук Подколзина А. С.( неоднократно), семинар "Математические вопросы кибернетики" под руководством академика О.Б. Лупанова, на 14-ой международной конференции "Проблемы теоретической кибернетики"в г. Пенза(2005), на VIII Международном семинаре "Дискретная математика и ее приложения"в Москве(2004),на Международная конференции "Интеллектуальные системы "в Москве(2002).
Публикации. Основные результаты работы опубликованы в пяти статьях: две статьи в журнале "Дискретная математика", одна статья в журнале "Интеллектуальные системы", издаваемом в МГУ, одна статья в сборнике материалов VIII Международного семинара "Дискретная математика и ее приложения,"одна статья в тезисах докладов 14-ой международной конференции "Проблемы теоретической кибернетики".
Структура и объем диссертации. Диссертация объемом 116 страниц состоит из введения, пяти глав, заключения и списка литературы из 24 наименований.
Связь длины установочного эксперимента с разбиениями Rk
Однако в примере Хиббарда, на котором достигается оценка 2- , использовался входной алфавит с п — 1 символами и оставался открытым вопрос о том, какова оценка для длины установочного эксперимента в случае, если ограничить рост входного алфавита. В первой главе работы исследуется вопрос о зависимости длины условного установочного эксперимента от длины входного алфавита. Установлена возможность понижения оценки Мура-Хиббарда уже при п — 9 входных символах. Показано, что порядок этой оценки сохраняется вплоть до двухбуквенного входного алфавита. Отметим, что Карацуба рассматривал задачу получения оценок для функции 1(К п), где через К п обозначен класс всех приведенных автоматов Мура с п состояниями [3]. Он показал, что 1{К) = (п- )(п- ) _j_ 2. В примере автомата, на котором достигается нижняя оценка, используется входной алфавит из п — 1 символов. В работе показывается, что квадратичный порядок из оценки Карацубы сохраняется вплоть до двухбуквенного входного алфавита, в то же время с помощью развитой в главе 1 техники можно установить возможность понижения верхней оценки в классе автоматов Мура с менее, чем п — 9 входными символами.
С задачей построения установочного эксперимента тесно связана задача синхронизации [5]. Ее можно рассматривать как установочную в классе автоматов без выходов. Кроме того понятно, что и в случае автоматов с выходами возможность склеивать состояния в процессе эксперимента оказывает существенное влияние на его структуру и сложность.
Во второй главе исследуются вопросы нахождения длины кратчайшей синхронизирующей последовательности для различных подмножеств состояний автоматов в различных классах. Рассматриваются две основные задачи: 1) получение оценок шенноновского типа для длины синхронизирующего слова; 2) получение средней длины синхронизирующего слова для почти всех автоматов.
При фиксированном г получен порядок для длины кратчайшего синхронизирующего слова для г — элементных подмножеств в классе всех автоматов с п состояниями. Установлена асимптотика длины кратчайшего синхронизирующего слова для г — элементных подмножеств для почти всех автоматов с п состояниями при г log2 log2 log2 п и п —ї со.
Саломаа [18] рассмотрел задачу синхронизации в классе автоматов над термами [1]. В работе рассмотрена задача о средней высоте синхронизирующего терма в автоматах над термами. Получена асимптотика длины кратчайшего синхронизирующего терма для г — элементных подмножеств для почти всех автоматов над термами с п состояниями при г log2 Iog2 Iog2 п и n — oo.
Отметим, что подобные задачи "усреднения"в дискретной математике рассматривались различными авторами. Так, например, в [12] рассматривается задача поиска усредненного значения веса автомата, в [7] — задача нахождения усредненного значения степени отличимости автомата. Однако, используемый в настоящей работе подход к решению задачи синхронизации имеет существенные отличия от походов указанных работ, продиктованные спецификой рассматриваемой задачи.
Понятно, что в общем случае длина условного установочного эксперимента не больше длины безусловного для того же автомата. В третьей главе рассмотрена задача о соотношении длин условного и безусловного установочных экспериментов. Получен порядок для максимального значения отношения длин безусловного и условного установочного экспериментов, а также получен порядок для значения отношения длин безусловного и условного установочного экспериментов для почти всех автоматов с п состояниями при п — со. В четвертой главе рассматривается задача определения длины установочного эксперимента для частичных автоматов. Такая постановка задачи может возникать, например, когда некоторые переходы автомата являются запрещёнными в том смысле, что переход по ним может привести к неисправностям автомата, В этом случае в процессе проведения эксперимента допускается подавать лишь слова, которые не приводят к повреждениям автомата. При — 0 получена асимптотика для длины условного установочного эксперимента для г — элементных подмножеств частичных автоматов, где п —число состояний автомата. При (1 — е),0 є 1 получен порядок длины условного установочного эксперимента для г — элементных подмножеств частичных автоматов. Получена верхняя оценка вида Clog n для остаточной степени отличимости равномерно для почти всех частичных автоматов с п состояниями и к выходными символами при п -» со. Указанная оценка обобщает оценку сверху Бардзиня вида С logfc п для степени отличимости равномерно для почти всех обыкновенных автоматов [13].
В пятой главе рассматривается задача нахождения оценок длины условного установочного эксперимента шенноновского типа при возможности произвольно перенаправлять р стрелок в диаграмме переходов автомата, либо произвольно менять значение функции выходов в р точках. Такая постановка задачи может возникать в случае, когда исследуемый автомат требуется упростить в смысле изменения его логики поведения таким образом, чтобы установочный эксперимент имел максимально простую структуру. Получены верхние и нижние оценки для длины условного установочного эксперимента при возможности произвольно изменить функцию выходов в р точках, либо поменять значение функции переходов в р точках. Отметим, что подобные вопросы о зависимости длины контрольного (тестового) эксперимента от локальных преобразований диаграммы переходов автомата рассматривались в работе [10]. Однако в этой работе рассматривались лишь преобразования, не выводящие автомат за рамки так называемого локально-порожденного класса [10], то есть новые переходы могли осуществляться лишь в состояния, смежные с исходным состоянием на старой диаграмме переходов. Возникшая в настоящей работе техника для решения подобных задач принципиально отличается от техники, используемой в [10].
Случай автоматов над термами. Вспомогательные определения и леммы
Проверим свойство 2). Покажем сначала, что при q ф q выполнено {p(q, а ) ф q . В самом деле, предположим, что это не так и рассмотрим слово а — а а . Пусть qr ф q — такое состояние, что p(q ,a ) = q . Тогда после подачи на вход автомата слова а, мы либо определим заключительное состояние автомата, либо сможем утверждать, что текущим состоянием автомата является одно из состояний множества Q = ip{Q \ {q ,q},a). Очевидно, что \Q \ п — 2. Тогда, согласно лемме 1, найдется условный установочный эксперимент Е для множества Q длины не большей " з — 3. Тогда, последовательно применяя эксперимент, состоящий в подаче слова а и затем эксперимент Е, построим эксперимент EQ, который будет установочным для всего множества состояний автомата 21. Длина эксперимента EQ не превосходит " "2 — 1, что противоречит тому, что 21 Smtn. Итак, для любого q ф q выполнено (р(д,а ) ф q .
Пусть теперь два состояния gi, 72 ф Я и входной символ а! таковы, что v( 7ba ) = (92ia )- Рассмотрим слово а = а а!. Подав слово а на вход автомата, мы либо определим его заключительное состояние, либо сможем утверждать, что текущим состоянием автомата является одно из состояний множества Q = (p(Q \ {q }}a ). Так как (p(qi,a ) = p(q2,a ) и qi,q2 Q \ {я }: т0 \Q \ п — 2 и найдется условный установочный эксперимент Е для множества Qr длины ие большей - — 3. Тогда, последовательно применяя эксперимент, состоящий в подаче слова а и затем эксперимент Е, построим эксперимент #0) который будет установочным для всего множества состояний автомата 21. Длина эксперимента EQ не превосходит -"2 — 1, что противоречит тому, что 21 Є Smtn. Итак, для любых двух состояний qi,q2 Є Q таких, что qi ф q и qi ф q выполнено p(qi, а ) ф 2, о ). Значит, свойство 2) установлено.
Перейдём к проверке свойства 3). Имеем следующие две возможности: a) найдётся входной символ а! ф а } который разбивает множество Q на две части { ? } U(Q \ {« }}, где f ф q ; b) каждый символ а Л либо пе разбивает множество Q, либо разбивает его следующим образом: {q } \J{Q \ { ? }} В первом случае применяя предыдущие рассуждения со словом а а , получим, что длина у. у. э. для автомата 21 не превосходит " — 1, что невозможно. Во втором случае проверим, что автомат %{а , Ь) является приведенным. В самом деле, рассмотрим два различных состояния q\ и qi из Q. Так как они отличимы в автомате 21, то найдется слово а из А такое, что (ч і)а) Ф Ф(Я2 а)- Обозначим через о/ префикс слова а без последней буквы. Нетрудно видеть, что либо (gi, о/) = q , либо p(#2i а ) = д , причем q (qi}a ) ф !p(q2,a ). Рассмотрим слово а" — а а . Очевидно, что оно отличает состояния q\ и ф в 21(а ,Ь). Итак, автомат Ща ,Ь) является приведенным и, следовательно, для него существует у.у.э. Нетрудно видеть, что любой такой эксперимент не может быть короче у.у.э. для 21, то есть 21(а ,6) Є Smin. Значит, свойство 3) установлено. Для 21 Є Sm,n при n 3 произвольным образом фиксированные, существующие согласно лемме 2 состояния q и символ а со свойствами 1), 2), 3), обозначим q (St), о (21) соответственно. Скажем, что слово а из входного алфавита автомата 21 = (Л, Q, Б, уз, і/») выделяет состояния 7i, ?2»... , 7г из множества Q, если для всех / Є Q из того, что для некоторого і Ег выполнено ij){q,ct) = ip q a) следует, что Пусть 21 = (A,Q,B,(p,ift) Sm,n и п 3. Для состояния q из Q длину кратчайшего слова о; из Л со свойством 7p(q,a) = # (21) назовем рангом состояния q и обозначим rang(q). Если для некоторого состояния q не существует ни одного слова а такого, что tp(q, а) — g (2l), то положим rang{q) = — 1. Очевидно, что максимальным значением для ранга может быть п — 1. Назовем ранговым расслоением множества Q автомата 21 следующее представление Q = Q01+1Q1 l+J Q"-11+) 3-1, где для всех і U {—1} имеем Qi {q Є Q, rang(q) — г}. Очевидно, что Qo = {g } Лемма 3. ІГо/ш 21 Є Sm,n и п 3, mo для рангового расслоения Q имеет место: 1) для всех г i?n-3 выполнено \QX\ = 1; і?) либо выполнено \Qn 2\ = 2, Qn_1 = 0, 5_1 = 0, либо выполнено \Qn 2\ = 1, jQ""1! = 1, IQ"1! = 0; либо выполнено \Qn-2\ = 1,\Яп 1\ = О, IQ"1! = 1. Доказательство. Ясно, что найдется вершина q\ ранга 1. В противном случае автомат 21 не был бы приведенным. Пусть а" Є A : tp(qi,a") = 5 (21). Рассмотрим слово а (21)а"а (21). Оно выделит состояния q и q\. Покажем, что состояния из множества Q/{g , q{\ могут под действием этого слова только некоторым образом переставиться. В самом деле, склейка состояний невозможна в силу леммы 2 и ни одно из состояний из 3/{g ,gi} не может перейти в q или в qi. Действительно, пусть это не так, тогда слово a (2t)aV(2l)aV(5l) или а (21)а"а (21)а (21) выделит уже 3 состояния, что невозможно в силу леммы 1. Кроме того ясно, что существует 72 Є Q/{q qi} и существует a " : p(q2,o/") = /i, то есть vang{q2) 2, но rangfa) ф 1. В самом деле, пусть vangi ) — 1. Тогда найдется о! " : (p(q2,a"") = q . Рассмотрим слово а (21)а"а (2t)a""a (21). Оно выделит три состояния 5 ) ?Ъ?2, что невозможно в силу леммы 1, так как длина указанного слова равна 5. По тем же соображениям 5ij = 1. Итак, (p(q2,a") = qi и rang(q2) = 2. Теперь рассмотрим слово а (21)а"а (21)а!"а"а (21). По соображениям, описанным выше, под действием этого слова множество ЯІ{ч іі)Ч2} перейдет в себя. В нем опять выделяется состояние 3 с rang{qj) — 3, про которое аналогично доказывается , что rang(q$) = 3- Продолжим аналогичные рассуждения до тех пор, пока оставшееся множество не будет содержать только состояния qn-i и qn-2- Среди них будет ,как минимум, одно состояние ранга п — 2, а про второе можно утверждать, что его rang равен п—2 или п—1. Все это проверяется по тем же соображениям, что были приведены выше с использованием леммы 1. Таким образом, для і Є En-z выполнено Ql = { &}, а также либо Qn 2 = {qn-2, qn-i} и Q""1 = 0 ,либо Qn 2 = {qn-2} и Q""1 = {qn-i}, либо Qn 2 = {qn-i} и Qn l = fe„_2}, либо Qn 2 = {qn-г}, Q""1 = 0 и Q"1 = {9n_2}, либо Qn 2 = {qn_2}) Qn l = 0 и Q l = {qn i}. Это равносильно утверждению леммы. Значит, лемма 3 доказана. Пусть 21 Є т)П,п 3 и г -з- Тогда, согласно доказанной лемме Q% = {її}- Обозначим состояние qi таким образом fc(2t). Обозначим Q = Q\Qo\Qi -\ Qn-з- Очевидно, что Q = 2. Имеем две возможности: 1) ровно одно из состояний множества \Q\ имеет ранг п — 2; 2) оба состояния из множества \Q\ имеют ранг п — 2. В первом случае через gn_2(2l) обозначим то из состояний множества Q, которое имеет ранг п — 2. Второе состояние множества Q обозначим (fa_i(2i).
Оценки длины условного установочного эксперимента для частичных автоматов
Таким образом, если q\ — ( bii))#2 = ( 2iJ2)i то в рассматриваемом случае i\ г2,іі Зі- Рассмотрим следующий процесс, в результате которого мы построим некоторое дерево Т высоты N. Вершинам дерева будут соответствовать состояния из Q. Ребрам из вершины v, соответствующей состоянию q} будем сопоставлять вариант заполнения диаграммы переходов для состояния q.
Корнем нашего дерева объявим вершину и, соответствующую q\. Из вершины v проведем вверх 24 ребра, соответствующие всем возможным вариантам заполнения диаграммы переходов в состоянии q\. Все новые вершины будут соответствовать состоянию q2. Возьмем одно из ребер I — (wi). Ему соответствует некоторый вариант заполнения диаграммы переходов в состоянии q\. Через w(l)t e(),n(/),s() обозначим соответствующие указанному варианту символы wqi, e7l, nqi, sqi соответственно. Для состояния ?2 теперь будем рассматривать только такие диаграммы, что wi ф eq2 ииіі ф пЯ2. Таких диаграмм, очевидно 12. Они будут соответствовать 12 ребрам, ведущим из вершины v\. Этим заканчивается 1-ый шаг нашего процесса. На этом шаге построины 2 слоя дерева Т.
Перед вторым шагом рассмотрим состояния q\ — ip(qi, wqi) и q\ = ip(q2,wg2). Все вершины последнего слоя дерева будут соответствовать состоянию q\. Здесь поступим аналогичным образом, т.е. заполним диаграмму переходов в q\ произвольным образом и далее в вершинах нового слоя, который будет соответствовать q\ заполним диаграмму так, что wqi ф eq\ и wqi ф nqx. Этим завершится второй шаг, на котором построены еще 2 слоя. Перейдем теперь от шага с номером к к шагу с номером к -f 1. Во-первых, определим состояния q\ = (p(qi l,w k-i) и q\ = (fiq -1, wQ -i) в случае, если первые координаты q\ и q$ не равны. В противном случае положим q\ = (gi"\ sj,"1)» gj = (rf"1» "1)- Д ее нетрудно видеть, что при таком определении состояний q\ и q\ выполнено q\ ф q\ для всех j к и Чі Ф Ч\ Для всех j к. В первом случае процесс построения 2-х новых слоев аналогичен описанному ранее, а именно: на первом новом слое вершины соответствуют q , и для них диаграммы переходов заполняются произвольно, а на 2-м слое вершины соответствуют 52 но здесь при заполнении диаграммы переходов имеется одна особенность. Если q$ и q имеют одинаковую первую координату, то требуем sqk ф nqk. Таких вариантов 18, т.е. из вершин дерева Т, соответствующих q%, будет выходить 18 ребер. Во втором случае (первая координата у q\ и q разная) заполнение обычное, т.е. с требованиями wqk ф eqk и wqk ф nqk. Таких вариантов 12. Далее еще надо рассмотреть случай q± q для некоторого j к. В этом случае на шаге к + 1 появятся не 2 слоя, а один слой, определенный по описанным выше правилам. Сделав 7 шагов описанного процесса, мы заполним менее 27 слоев. Остальные слои заполняются в соответствии с произвольным выбором диаграммы во всех состояниях, отличных от qi, q[ при j . 7 и 2» яі ПРИ j 7- Этим закапчивается построение дерева Т высоты N. Его листьям соответствуют полные заполнения диаграммы переходов. Установим следующие свойства построенного дерева Т. 1) Если 21 Є - 2(91)32)) то некоторому листу v дерева X соответствует диаграмма переходов автомата 21; 2) Количество листьев дерева Т не превосходят 18724 -7. Первое утверждение проверяется непосредственно и следует из того, что условия на разветвления в вершинах q соответствуют требованию о том, что d(4+1M+1) d(4,qi) Докажем второе утверждение. Про дерево Т можно сказать следующее. Для любого пути vi(viV2)v2 .. .vj -i от корня v к листу VN-I существует ровно 7 вершин с ветвлением равным 12 или 18. Под ветвлением в вершине ориентированного от корня дерева мы понимаем количество исходящих из вершины ребер. В остальных N — у вершинах ветвление равно 24. В тех вершинах, где ветвление равно 12, заменим ветвление на 18 следующим образом. Пусть ветвление в некоторой вершине z равно 12, то есть из вершины z исходят 12 ребер (zzi), (2:2:2),... (2:2:12). Добавим к дереву новые шесть вершин 2:13,...2:18 и ребра (2:213),(2:2:14),...(2:2:18) с копированием поддерева с корнем в вершине z\ на вершины гіз, - z\%. Получим дерево Т высоты N, количество листьев которого заведомо больше, чем у Т. Про дерево Т можно сказать теперь, что для любого пути 1 (7/11/2) ...i/jv-1 от корня к листу существует ровно 7 вершин с ветвлением, равным 18 и N — 7 вершин с ветвлением, равным 24. Проверим по индукции по N , что у любого такого дерева ровно 18724JV 7 листьев. В самом деле, убрав корень дерева, получим либо 24 поддерева высоты N — 1 с 7 ветвлениями порядка 18, либо 18 поддеревьев высоты ЛГ— 1 с 7— 1 ветвлениями порядка 18. По индукции в первом случае у каждого такого поддерева 18724ЛГ_1_7 листьев, а у исходного . Во втором случае у каждого из поддеревьев i8T"124iV 7 листьев, а у исходного дерева — 18 24 -7 листьев. Итак, утверждение 2 доказано. Очевидно, далее, что из утверждений 1 и 2 вытекает утверждение леммы. Значит, лемма доказана. Продолжим доказательство теоремы 4. Во-первых, проверим, что существует такая константа С О, что, \МУ I положив 7 — С log п получим Л/г ", — 1 при п — со. В самом деле, это равносильно тому, что т Ч — 0. Оцепим l-ZV J. Очевидно \Щ\ = Далее, \Q\ = п2, т.е. , в силу леммы 13, iV n п418724ЛГ 7. Значит, гд/ л Ш)7, Отсюда Уже непосредственно вытекает существование нужной константы С. Теперь, если мы установим, что для всех 21 Є М п выполнено /(21) Cin2logn, то теорема, очевидно, будет доказана. Итак, пусть 21 Є М2 п. Проверим следующее утверждение. Для любых г состояний из Q существуют 3 состояния qi7Q2,Qz из этих г, такие, что + 1). В самом деле, разобьем множество Q на квадраты с длиной стороны а так, чтобы они покрыли Q, но друг с другом не пересекались. Для этого учет границы квадратов должен быть таким На рисунке мы обозначили 1— неучитываемую границу и 2— учитываемую границу. Пусть в каждом квадрате менее двух точек из г отмеченных. Тогда 2(15] + 1)(К] + 1) г. Отсюда а 0, Положим а — [ ]+1, получим, что найдется квадрат, в который попадут 3 точки из г, и все попарные расстояния между ними не будут превосходить 2a, т.е. 2( л/ r + 1), что и требовалось. Далее, разобьем множество состояний Q на два пересекающихся подмножества Q\ и Qz следующим образом: Qi = {(і, J) Є Q : і + j-четно}; Q2 = {{hз) Є Q : ї + j-нечетно} Рассмотрим следующий процесе. Пусть на А; — ом шаге в рассмотрении находятся г N — к состояний. Выберем из них три в соответствии с требованием о том, чтобы все попарные расстояния между ними не превосходили 2( v/ гч + 1)- Из них трех состояний найдутся два - i,g2, лежащих в одном множестве Q\ или Qi- Для них мы найдем сначала слово а. длины менее Clogn, которое сократит расстояние между ними, т.е. d{qi,q%) d{ {q\ia),Tp{q2)a)). При этом легко видеть, что расстояние уменьшится как минимум на 2 и, кроме того, образы gi и qi опять будут лежать в одном из множеств Q\ или Q2, так как, очевидно, всегда q и ip(q, а) лежат в разных множествах Q\ и Qa- Далее, для этих образов мы также найдем слово длины менее Clogn, которое сократит расстояние между ними. В конце концов расстояние станет равным нулю или единице, но единицей оно быть не может, так как образы q\ и qi всегда лежат в одном из множеств Q\ или Q2- Второй случай будет означать, что состояния склеились и их останется меньше N — к — 1. При этом на к -ом шаге было получено слово о к, длины меньше Clognf л/7 t )i использованное для склейки qi и 2
Связи степени отличимости автомата с длиной установочного эксперимента
Так как gl{P, г, V) d, то каждый путь 7r(gs,a) 1 s г разбивается точками пересечения с другими путями не более, чем на d-\-1 частей. Стало быть, всего возникает не более, чем ({rd+r)d) отрезков путей, конкатенацией которых может быть образован путь n(qs,(3) при некотором s таком, что не имеет повторяющихся вершин и, следовательно, комбинировать для получения пути 7r(gs,/3) можно лишь различными отрезками путей из (rd + r)d возможных, отсюда следует, что количество различных слов /3, которые могут составить множество W, не превосходит r((rd+r)d+ly +r , а число таких множеств не превосходит 2rUr" +rJ"+1J . Лемма доказана.
Пусть Р D (n, т,Т, {а}). Заметим, что в каждом вершинном пути 7г (дпа:), определяемом по графу Р, вершины можно пронумеровать номерами от 1 до [Т] + 1 в порядке появления этих вершин в пути, так что вершина qr получит первый номер. Зафиксируем произвольный линейный порядок П на множестве А . Это можно сделать в силу счетности А . Пусть Ак = {ai, а ,... ,otk}— неупорядоченный набор из к попарно различных слов из А . Упорядочим слова из Ак таким образом, что а\ 02 с к в порядке 1. Разобьем каждый класс D (n,m,T,Ak) на подклассы D (n,m,r, Т, Afc, 5) по типу Е взаимного расположения путей 7t(qr,aj), где г є {1,2},J Є {1,2,..., к} , где тип Е определяется следующим образом. Пусть Р D {n, m,r, Т, {ai, о 2,..., otk})- Положим Е(Р) = (І і,.р2) fft-i) — упорядоченный набор наборов, где каждый из наборов Рл есть упорядоченный набор [L\, l?h%... Lrh) упорядоченных наборов четверок (si, S2,S3 54), определяемых следующим образом.
Положим S — ir(qiyah,+i). Далее S - есть подмножество тех вершин из 5, в которые ведет на графе Р, по крайней мере, одно ребро, встречающееся в путях Tt{qs,(Xj) при s 6 {1,2, ...г} и j /г, которое отлично от ребра, ведущего в эту вершину па пути ir(qi,ah+i)- Для каждого q 5" определим четверку (SI,S2J 53,64) следующим образом: s\— номер вершины q в вершинном пути 7r (qi,ah+i) в том смысле, о котором говорилось ранее. По определению 5 , существует такое р h, что q Є 7r (qs,ap). Выберем максимальное р с этим свойством. Полагаем теперь 52 - номер вершины q в ж (qr)ap),sz = 5,54 = р. Выписывая теперь полученные четверки в порядке возрастания sj, получаем набор L\. В случае, если S = 0, полагаем L\ равным пустому набору. Набор Щ при 2 z определяется аналогично. Нетрудно видеть, что подклассы D {n, m, г,Т, {ait не пересекаются при разных Hi и Ег, то есть имеем дело с разбиением класса Df(n, m, г, Т, ДА) на непересекающиеся подклассы. Рассмотрим граф Р Є D (n,m, г,Т, Д , Е). Заметим, что общее число четверок в наборах Щ при 1 г -1,и1 в г, образующих тип Е, если их выписать подряд, равно gl(P,r, Ак) — к(г — 1). Стало быть, типу Е можно приписать значение gl(r ,S,Ak) . Зафиксируем множество слов Ак = {( 1,( 2, и число р. Нетрудно оценить сверху число подклассов D {n,m,r,T, ДьЕ), для которых— Р-Это количество не превосходит (р + 1)гк(гк(Т-\-1) )р, что вытекает из сделанного замечания относительно общего числа четверок в наборах Lf, а также оценки числа четверок того вида, который был обозначен при описании понятия типа. Зафиксируем к и множество из к слов длины [Т] ({ai, е 2,... ,0}. При этом полагаем, что i\ . Обозначим
Сформулируем и докажем следующую лемму Доказательство. Без ограничения общности считаем, что «і а2 &к в порядке О. Пусть имеется некоторая стохастическая процедура G построения графов из D{n m), которая с одинаковой вероятностью приводит к построению любого графа из D(n,m). Заметим, что ра а а . Н " веРоятпость того, что в результате работы этой стохастической процедуры получится граф из D (n, mt r T, {ai, «2,.. a }, H). Обозначим Ті — [T]— целая часть числа Т. Рассмотрим следующий процесс Go построения графа из D[n}m). Процесс Go состоит из двух этапов. Первый этап состоит из гТ\к последовательных шагов и определяется следующим образом. Перед началом процесса имеем: множество Q, вершины qi Є Q при 1 і г, текущее множество ребер 5 = 0, текущая вершина g-1 = q\. Пусть а- первый символ слова а . Тогда первый шаг процесса состоит в равновероятном выборе любой из вершин множества Q в качестве концевой вершины ребра, исходящего из текущей вершины q — q\ и помеченного символом а. Выбранную вершину мы обозначим q1 и делаем ее текущей для второго шага, то есть полагаем q2 = q1 , а текущее множество ребер пополняем построенным помеченным ребром. Пусть проделаны г Т\ шагов процесса. На і + 1-ом шаге рассматриваем текущую вершину ql и г + 1-ую букву слова о: . Пусть это буква а . Тогда, если среди ребер текущего множества S нет ребра, исходящего из вершины q% и помеченного символом а , то на г + 1-ом шаге осуществляется равновероятный выбор вершины из Q, которую мы обозначим q% и которая становится текущей для следующего шага, то есть qi+1 = ql , а также происходит добавление в множество 5 ребра, исходящего из вершины q\ помеченного символом а и входящего в q1 , в противном случае множество S остается прежним, а текущей вершиной становится та, в которую ведет ребро из S, помеченное символом а, первая вершина которого есть q%. По окончании первых Ті шагов текущей полагаем qTl+l = g2 и процесс продолжается по тем же правилам. По окончании следующих Ті шагов полагаем q2Tl+l = /з и так далее. После первых тТ\ шагов полагаем qrTl+1 = q\ и процесс продолжается с заменой слова аі на oil- Еще через гТ\ шагов слово с 2 заменяется на слово а% и т.д. Второй этап состоит в последовательном просмотре вершин множества Q и выполнения для каждой из них следующей операции: если для некоторого символа а в множестве 5 нет ребра, ведущего из вершины q и помеченного символом а, то производится случайный выбор вершины q и добавления в множество S ребра, помеченного символом о, начинающегося в q и ведущего в q . Второй этап процесса 9 заканчивается, когда множество ребер S вместе с множеством Q образуют некоторый граф из D(n)m)) который и выдается на выходе стохастической процедуры SQ.
Нетрудно видеть, что описанный процесс с равной вероятностью приводит к построению любого графа из (гг,т).
Посмотрим теперь, какие ограничения на работу процесса о следует наложить, чтобы на его выходе появился граф из D (п,т,г,Т,{ofj a ,.. .а }эН). Для і 2[Т] необходимо потребовать, чтобы q% ф q3 для j і и q% ф qs при 1 s г. На шаге с номером 2Т\ необходимо потребовать, чтобы q2Tl = qTl , При 1Т\ Ї (7 4- 1)Хї, 2 / г — 1 необходимо требовать, что ql ф q3 для j і и ql ф qs при 1 $ г. Наконец, при і = IT\,Z I г необходимо иметь qiTl = qTl . Пусть теперь Н = ((L\, Lf,... L[), {Ь\, L%... Lr2),..., (L\_l} L\_v ... Ц._{) и (si,S2, 3,54) Lsh для некоторых 1 h к 1 и 1 s г. Тогда четверка (si,S2)S3 S4) накладывает ограничение на работу %, состоящее в том, что на шаге с номером і — r[T]h -\- (s 1)[Т] + si — 1 выбираемая вершина ql однозначно определяется тройкой (s2,S3i s4), а именно, ql = q3, где j — r[T](s4 — 1) -f [T](s3 — 1) + 2- Это вытекает непосредственно из определения типа Н, Так как всего четверок в наборах L\ ровно s — к(г — 1), то указанные ограничения вместе с аналогичным ограничениями на шагах с номерами (jr + І)Т\ при 2 I г образуют систему из 5 ограничений,каждое из которых состоит в том, что на некотором шаге / процесса QQ ребро, определяемое на этом шаге, не содержится среди ребер текущего множества ребер /-го шага и направляется в некоторую однозначно определенную вершину. Нетрудно понять, что каждое такое ограничение приводит к уменьшению вероятности появления графа Р D (n,m,г,Т, (ai,a2,.. .а;-),В) в п раз.