Установочные эксперименты с автоматами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи УДК 519.713

Кирнасов Александр Евгеньевич УСТАНОВОЧНЫЕ ЭКСПЕРИМЕНТЫ С АВТОМАТАМИ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

МОСКВА - 2005

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета Московского Государственного Университета имени М.В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор А.С. Подколзин.

Официальные оппоненты: доктор физико-математических наук,

профессор М.М. Глухов; кандидат физико-математических наук К.В. Коляда.

Ведущая организация: Саратовский Государственный

Университет им. Н.Г. Чернышевского.

Защита диссертации состоится 3 июня 2005 г. в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском Государственном Университете им. М.В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова(Главное здание, аудитория 14-08).

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ(Главное здание, 14 этаж).

Автореферат разослан 3 мая 2005 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор " 1 В.Н. Чубариков

Общая характеристика работы.

Актуальность темы. Настоящая работа посвящена исследованию свойств установочного эксперимента с автоматами. Если 21 = (A, Q, В, ip, ф)— конечный автомат, где А — входной алфавит, В —выходной алфавит, Q — множество состояний, ¡р,ф функции переходов и выходов, Тр : Q х А* —> Q, ф : Q Я. А* В*, - естественные продолжения функций ip и ф на слова из алфавита А*, то простым условным установочным экспериментом для автомата 21 называется ориентированное от корня дерево, вершинам которого приписаны подмножества множества Q и слова входного алфавита, а ребрам приписаны слова в выходном алфавите автомата, причем таким образом, что корню приписано все множество состояний, а листьям одноэлементные подмножества и для каждой неконцевой вершины г; дерева выполняется следующее условие : если av- слово, приписанное вершине v, то

1) для каждой вершины q е <?„, если ßq = то найдется ребро е = (г;го), выходящее из вершины v и оканчивающееся в вершине w такое, что ßq = ße и <p(q,av) 6 Qw, где Qv и Qw- подмножества состояний, приписанные вершинам v и w соответственно, ße— слово, приписанное ребру е;

2) если е = (vw) - ребро, выходящее из вершины v и оканчивающееся в вершине w, то Qw ф 0 и для каждого состояния с{ € Qw существует состояние q £ Qv такое, что а„) = q11.

Максимальная из сумм длин слов, приписанных вершинам ветвей описанного дерева, представляющего эксперимент, ведущих от корня к листу называется длиной эксперимента. Минимальную из длин простых установочных экспериментов для автомата 21 обозначим /(21). Если для автомата 21 не существует простого условного установочного эксперимента, то полагаем L(2t) = 0. Известно \ что для приведенных автоматов такой эксперимент существует всегда.

Простым безусловным установочным экспериментом для автомата 21 называется слово а е А", такое, что для любых двух состояний автомата 9i)92 € Q выполнено: если ф^\,а) — ф^2, а), то Xp{qx,a) = <&(q2, а). Слово а называется установочным для 2t. Кратчайшую из длин установочных слов для автомата 2t обозначим ¿u(2t). Если для автомата 21 не существует ни одного установочного эксперимента, то полагаем ¿„(21) = 0. Известно2, что

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

2 Нlb bard Т.Н 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 ]

если автомат приведен, то он имеет по крайней мере одну установочную последовательность.

Если К - некоторый класс автоматов, то обозначаем 1(К) = maxl(QI),

если такой максимум существует, в противном случае полагаем 1{К) = оо.

Аналогично, если К - некоторый класс автоматов, то обозначаем 1и(К) — тах1и(Ч1), если такой максимум существует, в противном случае полагаем

ЦК) = оо.

Остаточной степени отличимости автомата Si называется минимальное натуральное число h со свойством,что для любых двух состояний автомата qi, <72 автомата 21 выполняется одно из условий:

1) существует слово а такое, что 1(a) ^ h и ip(qi, а) Ф ф(д2, а);

2) существует слово а такое, что 1(a) ^ h и Tp(q\,a) — Щдъ, а).

Теория экспериментов с автоматами является достаточно хорошо развитой ветвью теории автоматов. Однако в последнее время, в связи с необходимостью верифицировать интернет-протоколы, появилось большое число работ, посвященных теории экспериментов с автоматами, например 3 4. В обзорной работе 3 приведены и обобщены практически все основные результаты теории экспериментов на сегодняшний день. В основном, авторы указанных работ рассматривают диагностические и тестовые эксперименты, то есть эксперименты, позволяющие либо полностью предсказать дальнейшее поведение автомата, либо отличить автомат от предъявляемого эталона. В обоих случаях установочный эксперимент играет роль строительного блока. Рассмотрим,например, тестовый эксперимент. Задача тестового эксперимента состоит в том, чтобы по предъявляемому автомату и некоторому эталонному автомата сказать, эквиваленты ли по поведению эти автоматы. Поскольку мы не знаем, в каком состоянии находится предъявляемый автомат, то сначала необходимо построить установочный эксперимент для эталона и применить его к тестируемому автомату. Если уже на этом этапе выявятся отличия поведения эталона и тестового автомата, то мы сможем заключить, что тестовый автомат и эталон неэквивалентны, в противном случае, мы проведем установочный эксперимент до конца и сможем теперь сформулировать гипотезу относительно текущего состояния тестового автомата. Дальше начинает работу непосредственно тестовый эксперимент. Аналогичная схема применяется и при построении

3D.Lcc, U Yannakaku Principles and methods of testing finite state machines. Proc of the IEEE, vol 84, 1090-1123, 1996.

*R.L. Rivcst R E Shaptrt Inference of finite state automata using homing sequences. Proc 21st Annual ACM Symp. on Theory of Computing, 411-420, 1989

диагностических экспериментов. На самом деле в работе5,при построении в некотором смысле алгебраической теории экспериментов с автоматами, показывается, что в определенном алгебраическом смысле установочные эксперименты, как "строительные блоки", необходимы при построении тестовых и диагностических экспериментов. Таким образом задача построения оптимизации установочного эксперимента является необходимой при построении и оптимизации диагностических и тестовых экспериментов.

Понятие установочного эксперимента условного и безусловного было введено Муром в работе 6. Там же доказывается теорема о том, что если Кп - класс автоматов с не более, чем п состояниями, то 1{Кп) < В

работе 7 Хиббард доказал, что для этого класса на самом деле имеет место равенство 1(Кп) =

Однако в примере Хиббарда, на котором достигается оценка "fo-1) использовался входной алфавит с в — 1 символами и оставался открытым вопрос о том, какова оценка для длины установочного эксперимента в случае, если ограничить рост входного алфавита. В первой главе работы исследуется вопрос о зависимости длины условного установочного эксперимента от длины входного алфавита. Установлена возможность понижения оценки Мура-Хиббарда уже при п — 9 входных символах. Показано также, что порядок этой оценки сохраняется вплоть до двухбуквенного входного алфавита.Отметим, что в работе 8 Карацуба рассматривал задачу о получении оценок для функции 1(К'п), где через К'п обозначен класс приведенных автоматов Мура с п состояниями. Он показал, что 1{К'п) = i"-1)^"'2) 4- 1. В примере автомата, на котором достигается нижняя оценка, используется входной алфавит из п — 2 символов. В главе 1 показывается, что квадратичный порядок из оценки Карацубы сохраняется вплоть до двухбуквенного входного алфавита, в то же время с помощью развитой в главе 1 техники можно установить возможность понижения верхней оценки в классе автоматов Мура с менее, чем с п — 9 входными символами.

С задачей построения установочного эксперимента тесно связана задача синхронизации9. Эту задачу можно рассматривать как установочную в

5 if. С. Грунский, В А Козловский, Г.Г. Пономлренко Представления конечных автоматов. Киев, Наукова думка 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,

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

Во второй главе исследуются вопросы о нахождении длины кратчайшей синхронизирующей последовательности для различных подмножеств состояний автоматов в различных классах. Рассматриваются две основные задачи:

1) получение оценок шенноновского типа для длины синхронизирующей последовательности;

2) получение средней длины синхронизирующего слова для почти всех автоматов.

При фиксированном г получен порядок для длины кратчайшего синхронизирующего слова для г— элементных подмножеств состояний в следующих двух классах автоматов : классе всех автоматов с п состояниями и классе автоматов с п состояниями, имеющих синхронизирующее слово сразу для всех состояний. Получена асимптотика длины кратчайшего синхронизирующего слова для г— элементных подмножеств состояний для почти всех автоматов с п состояниями при г < log2log2 log2n и п —► оо.

В работе10 Саломаа рассмотрел задачу синхронизации в классе автоматов над термами11. В работе рассмотрена задача о средней высоте синхронизирующего терма в автоматах над термами. Получена асимптотика длины кратчайшего синхронизирующего терма для г— элементных подмножеств состояний для почти всех автоматов над термами с п состояниями при г < log2 log2 log2 га и п —* оо.

Отметим, что подобные задачи "усреднения"в дискретной математике рассматривались различными авторами, например в 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 получена асимптотика для длины условного установочного эксперимента для г— элементных подмножеств состояний частичных автоматов, где п—число состояний автомата. При £ < ¿(1 — б), 0 < е < 1 получен порядок длины условного установочного эксперимента для г— элементных подмножеств состояний частичных автоматов. Получена верхняя оценка вида С logJ.fi для остаточной степени отличимости равномерно для почти всех частичных автоматов с п состояниями и к выходными символами при п —> оо. Указанная оценка обобщает оценку сверху Я. М. Бардзиня вида С к^* п для степени отличимости равномерно для почти всех обыкновенных автоматов.14

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

14Б А Трахтенброт, Я.М Бардзинъ Конечные автом«гы(Поведение н Синтез). Мбсква. "Наука". 1970.

1!Козловский В. А. О распознавании автомата относительно локально порожденного класса. Докл. АН СССР - 1981. - 258, 5. - С. 1047 - 1049.

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

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

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

Научная новизна. Все результаты работы являются новыми, основные результаты состоят в следующем:

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

2. Получена асимптотика длины кратчайшего синхронизирующего слова для г— элементных подмножеств состояний для почти всех автоматов с п СОСТОЯНИЯМИ при г < 1о§2 \og2 п и п —> оо.

3. Получен порядок для максимального значения отношения длин безусловного и условного установочного экспериментов. Получен порядок для значения отношения длин безусловного и условного установочного экспериментов для почти всех автоматов с п состояниями при п —» со.

4. При ^ —> 0 получена асимптотика для длины условного установочного эксперимента для г— элементных подмножеств состояний частичных автоматов, где п—число состояний автомата. При £ < |(1 — б), 0 < е < 1 получен порядок длины условного установочного эксперимента для г— элементных подмножеств состояний частичных автоматов.

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

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть полезны специалистам, занимающимся проблематикой экспериментов с автоматами таких научных учреждений, как Московский Государственный Университет им. М. В. Ломоносова, Институт прикладной математики им. М. В. Келдыша

РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С.Л. Соболева СО РАН, Нижегородского государственного университета им. М. В. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственного университета.

Апробация работы.

Результаты работы докладывались и обсуждались на следующих семинарах механико-матеметического факультета МГУ: семинар "Теория автоматов", под рук. академика В,Б. Кудрявцева( неоднократно), семинар "Элементы кибернетики "под руководством профессора, доктора ф.м. наук Подколзина А. С.( неоднократно), семинар "Математические вопросы кибернетики" под руководством академика О.Б. Лупанова, на 14-ой международной конференции "Проблемы теоретической кибернетики"в г. Пенза(2005), на VIII Международном семинаре "Дискретная математика и ее приложения"в Москве(2004),на Международная конференции "Интеллектуальные системы "в Москве(2002).

Публикации. Основные результаты работы опубликованы в пяти статьях: две статьи в журнале "Дискретная математика", одна статья в журнале "Интеллектуальные системы", издаваемом в МГУ, одна статья в сборнике материалов VIII Международного семинара "Дискретная математика и ее приложения,"одна статья в тезисах докладов 14-ой международной конференции "Проблемы теоретической кибернетики".

Структура и объем диссертации. Диссертация объемом 116 страниц состоит из введения, пяти глав, заключения и списка литературы из 24 наименований.

Основное содержание работы

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

Приведем основные понятия и обозначения, используемые в работе.

Пусть X и У конечные множества. Через |А"| обозначаем число элементов множества X, X х У— множество упорядоченных пар {(х,у),х е Х,у € У}- Словом в алфавите X будем называть любую упорядоченную последовательность элементов из множества X. Элементы последовательности, образующей слово, называем буквами слова. Длиной слова называем число его букв.

Пусть а = а1<22... ак — некоторое слово. Для каждого г такого, что 1 < г < к, префиксом слова а длины г будем называть слово а^ ■. ■ а,, которое будем обозначать а'. Суффиксом слова а длины г будем называть слово ... ак- Через а(г) будем обозначать г — ую букву слова а. Через 1(а) будем обозначать длину слова а.

Множество всех слов в алфавите X обозначаем X*.

Пусть а = Z1X2 /3 = У1У2 ■ ■ ■ У12 —два слова в алфавите X. Конкатенацией слов а и (3 называем слово Х\Х2 ■ ■ -хчу\у2 ■ ■ . yt2- Для операции конкатенации будем использовать знак *.

Натуральный ряд обозначаем N, множество натуральных чисел с нулем -

No- Множество действительных чисел обозначаем К. Если х € R, то через

[х] обозначаем целую часть числа х.

Пусть р— предикат на множестве X. Множество элементов х из X таких,

что р(х) = 1, будем обозначать таким образом: х Е Х]р(х) = 1. Пусть также

D - конечное подмножество натуральных чисел и р— некоторый предикат

на D. Для обозначения минимального и максимального элементов из D,

обладающих свойством, определяемым предикатом р, будем использовать

следующую запись: min{x € D\p(x) = l},max{x б D\p(x) = 1}.

Пусть X - множество и / : X —► No - некоторое отображение. Минимальное

из натуральных чисел п со свойством п > /(х) для всех х из X, если такое

существует, обозначим maxf(x). Если такого п не существует, то полагаем хеХ

тах/(х) = оо и считаем, что для всех натуральных п выполнено п < оо. хеХ

Начальный отрезок натурального ряда из г > 1 элементов обозначим Ет, таким образом Ет = {1,2,..., г}. Обозначим, далее, = {0,1,..., г — 1}. Для п € N, тп £ N,m < п обозначим Ет<п множество Еп \ Ет-1. Рассмотрим семейство конечных множеств Хп,п 6 N, и семейство предикатов рп,п € N на множествах Хп. Каждый предикат р„ определяет некоторое свойство Еп на элементах множества Хп. Обозначим Х'п = {х € Хп | р„(х) = 1}, то есть множества Х'п состоят из элементов множеств Х„, обладающих свойством Е„. Скажем, что для почти всех элементов из Хп, п € N выполнено свойство Еп, если —* 1 при п—* оо.

Мы будем использовать понятие о выполнимости некоторых свойств для почти всех элементов из некоторого семейства множеств применительно к автоматам. В этом случае считаем, что для рассматриваемых автоматов 21 = (A,Q,B,<p,i¡;) А — Em,Q = Еп,В = Ек при некоторых натуральных т, п, к. Два таких автомата 21 = {A, Q, В, ф) и 21' = (A',Q', В',1р',ф') называем одинаковыми, если А = A', Q = Q", В = В' и для всех q из Q, для всех а из Л выполнено <p(q,a) = ip'(q, а), ф(д, а) = ф'^,а). Число попарно разных автоматов с m входными символами, п состояниями и к выходными символами равно (пк)тк. Как правило,мы будем говорить о том,что для почти всех автоматов из некоторого класса Km,n,k автоматов с тп входными и к выходными символам имеет место определенная оценка для некоторых параметров этих автоматов. Например, в четвёртой главе параметром автоматов будет отношение длин безусловного

и условного установочного экспериментов для них. В качестве множеств Хп из предыдущего определения будем рассматривать множество автоматов Кт,п,к- В качестве свойства Еп будет выступать свойство автоматов из класса Кт:П}к, заключающееся в том, что для соответствующих параметров этих автоматов выполнены определенные неравенства.

Зафиксируем некоторый конечный детерминированный автомат 21 = (А, <5, В, <р,ф), где А — входной алфавит, В — выходной алфавит, <2 — множество состояний, <р,ф функции переходов и выходов.Мы будем использовать следующие естественные продолжения функций <рифя& слова входного алфавита Тр х А* С}, ф : х А* —* В*, определяемые следующим индуктивным образом: _

если а — а — однобуквенное слово, то <^(д, а) = <р(д, а), ф{д, а) — ф(я, о). Щя,") = <*о), оо)

ф(д, а) = ф(я, а0) * Ф0р(я, а0), ао).

Здесь ао означает последнюю букву слова а и ао - префикс слова а без последней буквы.

Там, где это не приводит к двусмысленности будем использовать обозначение Тр для отображения 29 х А* 2®

а) = {д : существует д7 € 5 такое, что = д}.

Основное внимание в первой главе уделяется вопросу о зависимости длины установочного эксперимента от числа входных символов. Обозначим АГт,п— класс приведенных автоматов с т, входными символами и п состояниями. Имеют место следующие теоремы

Теорема 1. Если п>9,тп<п-9, то 1(Кт, „) < - 1.

Теорема 2. 1(Кг„) > ^ + п - 5.

Во второй главе рассматривается задача о синхронизирующем слове для состояний автомата.

Пусть 21=(А,(3,В,<^, ф) - автомат. Пусть {дьд2, •.. ,дг} - некоторое множество состояний 21. Если для некоторого слова а из А* выполнено Тр(Я1,а) = <р(д2,а) — . а), то длину кратчайшего такого

слова назовем временем склейки данных г состояний. Введем функцию Та(<71,дг, • • •,Яг) , равную 0, если состояния дьЯ2, ■ ■ ■ ,Яг автомата 21 склеить нельзя, и равную времени склейки этих состояний в противном случае. Пару (21, {дьдг, • -. ,дг}) назовем г-инициальным автоматом. Пусть © — г—инициальный автомат. Тогда положим Т(Ъ) = Т<ц(дх, д2,..., дг).

Пусть класс автоматов с тп входными символами и п состояниями.

Введем в рассмотрение следующую функцию: 1д1(21, г) = тах Т<ц(д1, д2,..., дг).

{91,92, ,9г}£<г

Теперь определим такую функцию

1а1(т,п,г) = тах ЫЧ&.т). 9 у ЯбЛЬ,,. >

Теорема 3. Справедливы соотношения:

1) если г > 2, т > 2 фиксированы, то 1д1(т, га, г) х пг при га —> оо;

п — 2г Г-1

2)1д1(т, п, г) > (-—) при т>г, п>2г.

г — 1

Теорема 4. Для почти каждого 2-инициалъного автономного автомата 2$ выполнено Т(< >/п 1о£2 гс при п -+ оо.

Теорема 5. Если тп фиксировано и г < \og-i 1о§2 п то для почти каждого г-инициального автомата © с т входными символами выполнено: Т(58) ~ (г — 1 )1одтп при га —> оо.

Теорема 5 следующим образом обобщается на случай автоматов над термами.

Напомним определение автоматов над термами. Нас интересуют только автоматы без выходов, поэтому мы дадим определение именно таких автоматов.

Пусть конечное множество, к > 1 и для всех г таких, что 1 < г £ к, /Г' : х ■ ■ ■ х —> <5— некоторое отображение. Пара 21 =

4 V х

Г,

{/р, /22,..., /¿*}) называется конечным автоматом над термами без выходов. Отображения /,Г' называются входными отображениями.

С каждым отображением ■ <2 —* связан функциональный символ /< кратности г,. Эти символы играют роль букв входного алфавита в обычных автоматах.В дальнейшем, говоря о системе функциональных символов автомата, мы будем понимать систему всех функциональных символов, соответствующих входным отображениям автомата. Аналогом входного слова в случае автоматов над термами будет терм.

Дадим индуктивное определение терма над системой Р функциональных символов /р, 1 < г < к кратностей г^гг,... ,т>.

1) Функциональный символ /; есть терм для всех г таких, что 1 <i<k;

2) Если ТЬТ2,...,% суть термы над системой Р, то Л(Т\, ¿2, • ■., Т,)— терм над системой Р, если /а б

3) Те и только те выражения являются термами над системой Р, которые могут быть получены за конечное число шагов последовательным применением правил 1) и 2).

Термы, появляющиеся на шагах 1) и 2) описанного выше индуктивного процесса построения некоторого терма Т, называются подтермами терма Т.

Пусть Т - терм над системой Р функциональных символов некоторого автомата с множеством состояний ф. С каждым таким термом можно связать отображение <рт '■ Q Q следующим образом:

1) если Т = Ц' для некоторого /, е ^ то ~ - ■ Для всех q

Г,

из <?;

2) если Т = /*(ТьГ2,.. .,Т.), то = ■ • . Для всех 9 из <2-

Определим далее высоту к(Т) терма Т над системой Р.

1) если Т = для некоторого /, € то Л(Т) = 1;

2) если высоты термов 7\, Тг,..., Т$ определены иГ = /*(ТЬ Т2,..., Г,), то Л(Т) = шахМ^),..., Л(Г.)} + 1.

Зафиксируем теперь г состояний <7ь 921 • • • > 9г некоторого автомата над термами 21 = -Р"). Введем функцию времени склейки состояний 9ь ■ ■ ■, <?г следующим образом: если существует терм Т над системой .Р со свойством ^Рт{4\) = уНф) *=•■■ = <рт{<1г)), где отображение ^г определяется так, как указано выше по системе то минимальную из высот термов с таким свойством назовем временем склейки состояний в автомате 21 и обозначим Та(<7ъ?2> • • •, 9г). В противном случае положим Та(<7ьФг, • • ■ >9г) = 0.

Наконец, введем определение г— инициального автомата над термами. Пару (21, {дь • • ■) <7г}), состоящую из автомата над термами 21 и неупорядоченного набора из г его состояний, назовем г— инициальным автоматом над термами. Пусть 5$ = (21,{дх,<й,... ,<?,-}) - г инициальный автомат над термами. Обозначим Т(®) = Та(дь ■ • •, 9г). Имеет место теорема.

Теорема 6. Если к, я, п, гг,..., г* € Р1, к > 1, Я = таа;{г1, гг,..., г*}, Я > 1 и г < 1о^21о§21о§2 п, то для почти всех г - инициальных автоматов Ъ над термами с к входными отображениями кратностей Т\,гч,... ,Тк справедливо + С\ < Т(®) < logдlog2(n) 4- Сг при п -* оо, где

С\, С<1~ некоторые константы.

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

Рассмотрим класс Кт<п^ приведенных автоматов с т входами, п состояниями и к выходами. Также рассмотрим класс Кп приведенных автоматов с п состояниями.

Пусть фиксирован автомат 21. Обозначим а{21) = Т^ц' а(п) = таха(Ш).

Доказываются следующие две теоремы:

Теорема 7.

Имеет место | < ст(п) < п.

Теорема 8. Если т, к фиксированы и п —+ оо, то для любой константы С > 15, для почти всех автоматов 21 из Кт1п,к выполнено <7(21) < С.

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

Автомат 21 = (Л, В, 1р, ф) с частично определёнными функциями и ф называется частичным. Множество пар (д, а), для которых ¡риф определены, назовём множеством допустимых переходов и обозначим Ау(21). Слово а длины г допустимо для q, если для всех г из Ег выполнено (^(<7, а'-1),а(г)) € 21). Если й - граф переходов некоторого частичного автомата 21 = (А,(2,В,(р,ф), то такой граф будем называть автоматным и обозначать (А, <3, <р), а через функцию переходов соответствующего автомата.

Множество пар на которых не определены функции <р и ф,

обозначим Ау(%).

Рассмотрим множество С?' С С}. Слово а назовём частично разрешающим для множества если оно является допустимым для всех состояний множества (2 и либо найдутся два состояния € и да € С?' такие, что , а) = "), либо найдутся два состояния из множества такие, что ф(дьа) -ф- ф{ц2,а). Для каждого подмножества О1 С обозначим через 1р(0>) длину кратчайшего частично разрешающего слова для множества <5', если существует, по крайней мере, одно такое слово. В случае, когда для множества С}' не существует частично разрешающего слова, положим 1Р{0>) = 0. Через 1Р{% г) обозначим ^ 1р{Я')- Эту величину назовём

степенью частичной разрешимости автомата 21 порядка г.

Введём по аналогии понятие разрешимости порядка г. Рассмотрим множество О! С Слово а назовём безусловным установочным экспериментом для множества б?', если оно является допустимым для всех состояний множества и для любых двух состояний € и дг 6 О* либо ^(</1,а) = а), либо ^(<7ьа) Ф{Я2,ос). Для каждого подмножества С}' Я <Э обозначим через ¿{Т(21, ф') длину кратчайшего безусловного установочного эксперимента для множества если существует, по крайней мере, один такой эксперимент . В случае, когда для множества О' не существует ни одного безусловного установочного эксперимента, положим

1?(Ъ,0') = 0.

Через (21, г) обозначим величину ^ шах 1^(21, С?). Эту величину назовём степенью разрешимости автомата 21 порядка г. Нетрудно видеть,

что при г ~ п степень разрешимости совпадает с длиной безусловного установочного эксперимента для автомата 21.

Введём понятие условной разрешимости. Рассмотрим множество фо Я С?. Ориентированное от корня дерево Т назовём условным установочным экспериментом для множества состояний С}о автомата 21, если каждой вершине V приписано подмножество состояний С2У и слово а„, а каждому ребру е приписано слово /?е из выходного алфавита В таким образом, что выполняются следующие условия:

1. Слово Оу является допустимым для всех вершин множества

2. Если е-ьщ- ребро, выходящее из вершины V и (¿е = {д € : т/>(<?, а) = Д.}, то £?е Ф 0 и <3,,! = Тр(С}е,а) и, кроме того, для любого состояния <7 е <3и найдётся ребро е, выходящее из вершины V такое, что 1/>(д, а) = Д..

3. Корню дерева приписано множество С?о•

4. Концевым вершинам дерева Т приписаны одноэлементные множества.

Если существует хотя бы один условный установочный эксперимент для множества состояний (¿о автомата 21, то максимальную из сумм длин слов, приписанных вершинам ветвей, ведущих от корня к листьям таких деревьев, назовём длиной условного установочного эксперимента для множества С?о и обозначим ^(21, <5о)- В противном случае положим Р""(21, Qo) = 0. Наконец положим Л""(21, г) = шах Р^Ш,, Ш-

Обозначим К класс частичных автоматов, у которых любые два состояния отличимы. Введём функии

1рг(п, г) и г, т) следующим образом ¿^"(п, г) = ^ тах ^(21, г), ¿^(п, г, (¿, т) = тах Р""(Я, г).

Зафиксируем автоматный граф <7 = (Л, <5, </?) с = га и \А\ = т, где т > 2 и выходной алфавит В с \В\ = А;, где к > 2. Множество всех частичных автоматов © = (А, В, уз, ф) с автоматным графом С? обозначим 3(С, к). Через к, г, Я) обозначим подмножество множества А;), состоящее из тех автоматов для которых 1Р(ГВ,г) > Я Через ¿"(С, к, г, Л) обозначим подмножество множества £(£?, Л), состоящее из тех автоматов 93, для которых > Я.

Скажем, что равномерно почти все частичные автоматы с ш > 2 входными символами и А; > 2 выходными символами имеют степень частичной разрешимости порядка г не больше Я(п), если выполнено следующее предельное соотношение: - 0 при п оо.

Доказываются следующие результаты

Теорема 9. Если та > 2 и к > 2, то найдутся константы С\ > 0 и С% > 0

такие, что:

1) равномерно для почти всех частичных автоматов с т входными и к выходными символами степень частичной разрешимости порядка г не превосходит (С\г2 togfc п)Т при п—*оо;

2) неверно, что равномерно для почти всех частично-определённых автоматов с т входными и к выходными символами степень частичной разрешимости порядка г не превосходит C2log2 " при п оо.

Следствие 1. Если тп > 2 и к > 2, то найдутся константы С\ > 0 и С% > 0 такие, что

1) равномерно почти все частичные автоматы с т входными символами и к выходными символами имеют степень частичной разрешимости порядка 2, не превосходящую С\ log¡¿ п при п —> оо;

2) Неверно, что равномерно почти все частично-определённые автоматы с т. входными символами и к выходными символами имеют степень частичной разрешимости порядка 2, не превосходящую С2 logj. п при п —+ со.

Можно было бы предположить, что равномерно степень разрешимости не превосходит r(CV2 log* п)г, в частности, при г = 3, верхняя граница для равномерной оценки могла быть: Clog¿n. Следующая теорема показывает, что указанное предположение неверно.

Теорема 10.

Если тп = 2 ,к — 2 и г = 3, то для любого п > 4 существует такой

автоматный граф Gen вершинами и т. входными символами, что |S'(G.fc.r,n-3)| ^ i

Wh -

Теорема 11. Имеют место оценки:

1)Пп,г)< £ Q;

1<»£г

2)1^ (п,г) > Снесли г < § ;

3)^(71,7-) >С1 еслиг>\.

Доказываются следующие следствия из теоремы 12. Следствие 2.

Если ^ -> 0 при ti —► оо, mo ^(п, г) ~ Следствие 3.

Если < ± -е,0 < е < mol^far) ж СГп.

Таким образом при ^ —> 0 полученная оценка асимптотически точна,

при ^<£-б,0<б<5 оценка точна по порядку.

В теореме 4 устанавливается , что в случае г = 2 порядок оценки из теоремы 12 сохраняется даже при одном запрете на функцию переходов и 3-х входных символах.

Теорема 12.

Имеет место 1рг(п, 2,1,3) > у.

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

Пусть дан автомат 21. Обозначим через /г(21) степень отличимости автомата 21.

Введем понятие остаточной степени отличимости автомата 21. Предположим, что для любых двух состояний автомата дьдг автомата 21 выполняется одно из условий: _ _

1) существует слово а такое, что 1(а) < Л и тр(д1, а) ф ф(дг, а);

2) существует слово а такое, что 1(а) ¥?(<7ь а) = а)-

Пусть также Л - минимальное число с таким свойством. В таком случае скажем, что остаточная степень отличимости автомата 21 есть Л и будем писать Л/,„(21) = Л.

Введем понятие Яг - неполного автомата. Пусть дан автомат 21 = (А,(}, В, 1р,ф). Занумеруем его компоненты числами от 1 до А;. Таким образом = и д„ где (5, - различные Я1 компоненты автомата 21. Для

каждого состояния д € <3 определим отображение А —* {1... к} следующим образом- /,(а) = г, если а) € С2г. Автомат назовем Яг - неполным, если найдется отображение / : А —► {1... Л} такое, что / ф /, при q€.Q.

Введем понятие класса автоматов-идентификаторов. Автомат 21 = (Л, В, у, V) назовем идентификатором, если найдется такое состояние qo автомата 21, что при д Ф до из € существует слово а из А* такое, что <р(д,а) = до и существуют Ьо, Ь\ е В такие, что &о ф 61, при д ф до и а из А выполнено ф(д, а) = Ьо а существует <ю из А такое, что выполнено ФЫ,а0) = Ь1.

Для автомата 21 = {А, ф, В, у, ф) обозначим ЛГ(21, р)- класс автоматов 21' -- (А, С?, В, <//, таких, что существует не более р пар (д, а), для которых ¥?(д,о) ф^(д,а).

Также для автомата 21 = (Л, ф, В,р,ф) обозначим ЯГ'(21,р) следующий класс автоматов. Рассмотрим произвольный бесконечный алфавит В', содержащий алфавит В в качестве подмножества. В класс автоматов К'

включаются все те и только те автоматы 21' = {A, Q, В", <р, ф') с В" С В' и В С В" для которых существует не более р пар (q,a) таких, что i/)(<j, а) ф

Обозначим htr($L,p) = min/i/,„(®), где минимум берется по всем автоматам 93 из класса K(QL,p). Также обозначим /irtr(2t,p) = min/i(?8), где минимум берется по всем автоматам 58 из класса Ä"'(2l,p).

Обозначим fir(2l,p) = min ¿(25), где минимум берется по всем автоматам ® из класса К(%.,р). Также обозначим i"r(2t,p) = minZ(©), где минимум берется по всем автоматам © из класса K'(<ä,p).

Рассмотрим функцию htr(n,m,p) = max htr($L,p), где максимум берется в классе Лг-неполных автоматов с п состояниями и тп входными символами. Аналогично введем функцию h'tT(n,p) = max/i'tr(2t,p), где максимум берется в классе всех автоматов 21 с п состояниями.

Обозначим Л£|(п,р) = max/itr(2t,p), где максимум берется по всем автоматам идентификаторам с п состояниями и аналогично hft*d{n,p) = max/i'tr(2l,p), где максимум берется по автоматам-идентификаторам с п состояниями.

Обозначим теперь Р^т.р) = тах/'г(й,р), где максимум берется по i?2~ неполным автоматам с п состояниями, и тп входными символами. Также обозначим 1%{п,р) = maxZir(2t,p), где максимум берется по классу автоматов- идентификаторов с п состояниями. Обозначим 1Пг(п,р) = max ¿'(21, р), где максимум берется по всем автоматам с п состояниями. Наконец обозначим /''¿(п,р) = max ¿''¿(21, р), где максимум берется в классе автоматов-идентификаторов с п состояниями.

Введем обозначение д(п,р) для следующей функции двух переменных Г i^Ti] + если я — 1 не делится нацело нар +1, = Иначе. Сформулируем теперь основные результаты главы 5.

Теорема 13.

Существуют положительные константы С\, Ci б М, такие, что выполняются следуюише неравенства:

1)^2 < AtrK m,P) < ;m"p'og2P;

2)^ < h,lr{n,p) < fiüJbZ.

Теорема 14. Имеет место:

g(n,p) < A5(n,p) < g(n,p) + 1, 5(n,p) ^ h'^{n,p) < p(n,p) + 1.

Теорема 15.

Существуют

положительные константпы С\, С2, Сз £ R, такие, что

выполняются следующие неравенства: 1 )ltr(n,m,p) <

2)1»(п,п,р) > Sf;

3)itr(n,2,P) >

< l'tr(n,p) < с'п2>ЪР.

Теорема 16.

Имеет место:

(V + l)g(n,p)(g(n,p) - 1)/2 < l¡rd(n,p) < min{ng(n,p), =^1},

(Р + 1Ж»,Р)С?(».Р) - 1)/2 < l'Un,p) ^ "fcfïl}.

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

Благодарности

Автор выражает глубокую благодарность академику, доктору физико-математических наук В.Б. Кудрявцеву и профессору, доктору физико-математических наук А. С. Подколзину за постановку задач, постоянную поддержку и внимание к работе, ценные замечания и полезные обсуждения.

Статьи автора по теме диссертации.

1. А.Е. Кирнасов О зависимости длины условного установочного эксперимента от локальных преобразований его диаграммы переходов и функции выходов. // Ж. Дискретная математика, 2005, том 17, №2, с. 142157.

2. А.Е. Кирнасов О склейке состояний автомата. // Ж. Дискретная математика, 2003, №4 с. 66-83.

3. А.Е. Кирнасов О длине простого условного установочного эксперимента. // Ж. Интеллектуальные системы, 2000, Т.5, вып. 1-4, стр. 199-212.

4. А.Е. Кирнасов Установочные эксперименты для частичных автоматов. // Проблемы теоретической кибернетики. Тезисы докладов 14-ой международной конференции(Пенза, 2005) - М.: изд-во МГУ, стр. 61.

5. А.Е. Кирнасов Установочные эксперименты с автоматами. // Материалы VIII Международного семинара "Дискретная математика и ее приложения", 2004, стр. 272 - 275.

$-6860

РНБ Русский фонд

2006-4 5256

Издательство ЦПИ при механико-математическом факультете МГУ им М.В. Ломоносова. Подписано в печать /&.№{. 0£ Формат 60x90 1/16. Усл. печ. л. 1,0

Тираж 100 экз. Заказ 2/

Лицензия на издательскую деятельность ИД В 04059, от 20.02.2001г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение.

§1. Основные понятия и обозначения.

§2. Результаты работы.

§3. Предыстория вопроса.

Глава 1. Сложность условного установочного эксперимента для различных классов автоматов.

§1. Введение.

§2. Основные определения и результаты.

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

§4. Доказательство теорем 1 и 2.

§5. Доказательство теорем 3 и 4.

§6. Доказательство теорем 5 и 6.

§7. Связь длины установочного эксперимента с разбиениями Rk.

Глава 2. Сложность установочного эксперимента для автоматов без выхода.

§1. Введение.

§2. Основные понятия и результаты.

§3. Доказательство теорем 1,2 и 3.

§4. Доказательство теоремы 4.

§5. Вспомогательные определения и леммы.

§6. Доказательство теоремы 5.

§7. Случай автоматов над термами. Вспомогательные определения и леммы.

§8. Доказательство теоремы о времени склейки г состояний автомата для почти всех автоматов над термами.

§9. Некоторые оценки для времени склейки г состояний в автоматах над термами.

Глава 3. Соотношение сложностей условного и безусловного экспериментов.

§1. Введение.

§2. Основные определения и формулировка результатов.

§3. Доказательство теоремы 1.

§4. Доказательство теоремы 2.

Глава 4. Установочный эксперимент для частично-определённых автоматов.

§1. Введение.

§2. Основные определения и результаты.

§3. Понятия и результаты.

§4. Доказательство теорем 1 и 2.

§5.0ценки длины условного установочного эксперимента для частичных автоматов.

Глава 5. Установочные эксперименты для автоматов с изменяемой логикой поведения.

§1. Введение.

§2. Основные определения и результаты.

§3. Понятия и результаты.

§4. Связи степени отличимости автомата с длиной установочного эксперимента.

§5. Теорема об условной степени отличимости.

§6. Доказательство теоремы 1.

§7. Доказательство теоремы 2.

§8. Доказательство теорем 3 и 4.

§1. Основные понятия и обозначения.

Настоящая работа посвящена исследованию свойств установочного эксперимента с автоматами.

Договоримся о следующих используемых в работе обозначениях и понятиях.

Пусть X и Y конечные множества. Через \Х\ обозначаем число элементов множества X, X х Y - множество упорядоченных пар {(ж,у),х Е Х,у Е У}, Хк - множество упорядоченных к—элементных наборов {(xi, ®2» ■ • • 1 Хк), Щ Е X, 1 < i < к}.

Словом в алфавите X будем называть любую конечную последовательность элементов из множества X. Элементы последовательности, образующей слово, называем буквами слова. Длиной слова называем число его букв.

Пусть а = а\а2. аь — некоторое слово. Для каждого г такого, что 1 < i < к, префиксом слова а длины i будем называть слово а\й2. .щ , которое будем обозначать аг. Суффиксом слова а длины i будем называть слово ak-i+iak-i+2 • • • Через а(г) будем обозначать г—ую букву слова а. Через £(а:) будем обозначать длину слова а. Множество всех слов в алфавите X обозначаем X*.

Пусть а = Х\Х2 •. -Xi^P = 2/12/2 • • • Vi2—Два слова в алфавите X. Конкатенацией слов а и (3 называем слово Х\Х2 . х^у\у2 . ■. Vi2. Для операции конкатенации будем использовать знак *.

Натуральный ряд обозначаем N, множество натуральных чисел с нулем обозначаем No- Множество действительных чисел обозначаем М. Если х € М, то через [ж] обозначаем целую часть числа х. Начальный отрезок натурального ряда из г > 1 элементов обозначим Ег, таким образом, Ег = {1,2,., г}. Обозначим далее = {0,1,., г — 1}. Для п Е N, т G N, тп < п обозначим через Ет>п множество Еп \ Ет-1.

Пусть р — предикат на множестве X. Множество элементов х из X таких, что р{х) = 1, будем обозначать {х Е X | р{х) = 1}. Пусть также D - конечное подмножество натуральных чисел и р — некоторый предикат на D. Для обозначения минимального и максимального элементов из D, обладающих свойством, определяемым предикатом р, будем использовать запись: шт{ж Е D | р(х) = 1}, тах{а: Е D | р{х) = 1}. Пусть X - множество и / : X —> N - некоторое отображение. Минимальное из натуральных чисел п со свойством п > f(x) для всех х из X, если такое существует, обозначим шах/(ж). Если такого п не существует, то полагаем maxf(x) = oo и считаем, что для всех натуральных п выполнено п < оо.

Рассмотрим семейство конечных множеств ХП7 п Е N и семейство предикатов рп, п Е N на множествах Хп. Каждый предикат рп определяет некоторое свойство Еп на элементах множества Хп. Обозначим Х'п = {х €

Хп | Рп(х) = 1}, то есть множества Х'п состоят из элементов множеств

Хп, обладающих свойством Еп. Скажем, что для почти всех элементов из х' I

Хп, п Е N выполнено свойство Еп, если —» 1 при п —> оо.

Мы будем использовать понятие о выполнимости некоторых свойств для почти всех элементов из некоторого семейства множеств применительно к автоматам. В этом случае считаем, что для рассматриваемых автоматов 21 = (A, Q, В, (р,ф) А = Ет, Q = Еп, В = Ek при некоторых натуральных т, п, Класс всех автоматов с этим свойством обозначим через Fo- Два автомата 21 = (A,Q, В,ср,ф) и 21' = (A',Q',(р',ф') называем одинаковыми, если А = A',Q = Q', В = В' и для всех q из Q, для всех а из Л выполнено <p(q,a) = cp'(q,a),xp(q,a) = ф'{с[,а). Число попарно разных автоматов с т входными символами, п состояниями и к выходными символами из F равно (пк)тк[ 1]. Как правило, мы будем говорить о том, что для почти всех автоматов из класса = Кт^к П Fq имеет место определенная оценка для некоторых параметров этих автоматов, где через обозначен класс всех автоматов с т входными, к выходными символам и п состояниями. В таком случае, мы также будем говорить, что указанная оценка параметров имеет место для почти всех автоматов из класса Например, в четвёртой главе параметром автоматов будет отношение длин безусловного и условного установочного экспериментов для них. В качестве множеств Хп из предыдущего определения будем рассматривать множество автоматов Fm,n,k- В качестве свойства Еп будет выступать свойство автоматов из класса Fm,п,к, заключающееся в том, что для соответствующих параметров этих автоматов выполнены определенные неравенства.

Пусть некоторое множество X представляется в виде прямой суммы некоторых своих непустых подмножеств : X = Xi • • • Тогда неупорядоченный набор множеств Т = {Xi, Х2,. Хк} будем называть разбиением множества X. Мы будем также использовать следующую запись для определения разбиений: Т = {Xi | 1 < i < к}.

Пусть Т\ = {Xi | 1 < i < г'о},Т2 = {Yj | 1 < j < jo}—два разбиения множества X. Тогда пересечением разбиений Т\ и Т2 назовем следующее разбиение Т3 = {Xi П Yj | 1 < г < г'о, 1 < j < jo}. Предполагаем, что в разбиение Т3 включаются только непустые пересечения Xi П Yj.

Договоримся также о следующих определениях и обозначениях из теории графов. Для графа G через V(G) обозначим множество его вершин. Пусть X - некоторое множество и г : V{G) —> X - некоторое отображение. Припишем каждой вершине v графа G элемент t(v) из множества X. Таким образом размеченный граф обозначим t(G).

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

Ориентированным к корню деревом называем ориентированное дерево Т с выделенной вершиной г - корнем такое, что для любой вершины v дерева существует ориентированный путь, ведущий от v к г.

Длину ориентированного пути, ведущего от корня дерева к некоторой его вершине(или от вершины к корню), назовем высотой вершины. Листовой или концевой вершиной корневого дерева будем называть такие его вершины, из которых не исходит ни одного ребра. Ветвлением корневого дерева в вершине v назовем количество исходящих из нее ребер.

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

Перейдём к определениям, связанным с экспериментами для автомататов. Зафиксируем некоторый конечный детерминированный автомат 21 = (A,Q, В,(р,ф) [1], где А — входной алфавит, В — выходной алфавит, Q — множество состояний, а ср, ф — функции переходов и выходов. Мы часто будем использовать естественные продолжения функций (р и ф на слова входного алфавита Тр : Q х А* —> Q, ф : Q х А* В*, определяемые следующим индуктивным образом: если а = а — однобуквенное слово, то ip(q, а) = ip(q, а),ф(д, а) = ф(д, а);

Щя,а) = <p(cp(q,ao),a о);

Ф(Я,= ф{я, а0) * ф{Щя, а0), а0).

Здесь ао означает последнюю букву слова аиао- начальный отрезок слова а без последней буквы.

Там, где это не приводит к двусмысленности, будем использовать обозначение Тр для следующего отображения х А* :

Tp(S, а) = {q : существует q' G S такое, что Tp(qr,a) = q}. Из контекста будет ясно, о каком отображении идет речь. Пусть 21 = (A,Qo, В,сро,фо) и 03 = (A, Qi,B,(pi,ifii)— два автомата таких, что Qo П Qi = 0. Тогда автомат С = (Л, Qq U Qi, В, (p2, Ф2) назовем прямой суммой автоматов 21 и 03 и будем писать С = 21ф23, если выполняются следующие условия:

1) если q G Qo, то ip2(g, а) = (po(q, a), а) = ф${(1, а) для всех а из А\

2) если q G Qi, то (q, a) = </?i(g, а),ф2(q, a) = a) Для всех a из A.

Пусть 21 = (A, Qo, В,(ро,фо) и 95 = (A, Qi,.B, — два автомата таких, что Qo С Qi- Скажем, что автомат 21 является подавтоматом автомата 05 при выполнении следующего условия: если q е Qo, то (fi(q, а) = ipo(q, a), а) = фо(д, а) для всех а из А;

Пусть 21 = (Ao,Qo,Bo,(po,i/>o) и 95 = (Аи Qb <рь два автомата таких, что существуют взаимнооднозначные отображения fa : Ао —> Ait fb' Bq Bi, fq : Qo Qb такие, что выполняется следующее условие: если g € Qo, a G Л0, то fq(vo(q,a)) = ipi(fq(q)} /в(а)), /ь(Фо(я,<0) =

Ш./«(«)) (Ч

В таком случае, автоматы 21 и 95 называются изоморфными. Если от отображений /а, /ь и требовать лишь выполнения свойства (1) и не требовать взаимной однозначности, то скажем, что тройка (fa,fb,fq) осуществляет гомоморфизм автомата 21 на 25. В частности, если Aq = А\,Во = £?i,/a, fb — тождественные отображения, то будем говорить, что отображение fq порождает гомоморфизм автомата 21 на автомат Ш.

При к 6 N через Rk обозначаем следующее отношение эквивалентности на множестве состояний автомата: состояния qi,q2 из Q эквивалентны в отношении Rk тогда и только тогда, когда для всех слов a Е А* с 1(a) = к выполнено ф{дi,a) = ф^2,а).

Введем понятие остаточной степени отличимости автомата 21. Предположим, что для любых двух состояний автомата qi,q2 автомата 21 выполняется одно из условий:

1) существует слово а такое, что 1(a) ^ h и а) ф ф^2, £*);

2) существует слово а такое, что 1(a) ^ h и 7p(q\,a) = lp(q2,a). Пусть также h - минимальное число с таким свойством. В таком случае скажем, что остаточная степень отличимости автомата 21 есть h и будем писать

Ьцп(Щ = h.

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

Условным установочным экспериментом для множества S состояний автомата 21 называется конечное ориентированное от корня дерево, вершинам которого приписаны подмножества множества Q и слова входного алфавита, а ребрам — слова в выходном алфавите автомата, причем таким образом, что корню приписано множество S, листьям — одноэлементные подмножества и пустые слова и для каждой нелистовой вершины v дерева выполняется следующее условие : если av~ слово, приписанное вершине v, то

1) для каждого состояния q £ Qv, если (3q = ip(q,av), то найдется ребро е = (vw), выходящее из вершины v и оканчивающееся в вершине w такое, что (3q = Ре и 7p(q,av) Е Qw, где Qv и Qw- подмножества состояний, приписанные вершинам v и w соответственно, /Зе— слово, приписанное ребру е;

2) если е = (vw) - ребро, выходящее из вершины v и оканчивающееся в вершине то Qw ф 0 и для каждогосостояния g' G Qw существует состояние q £ Qv такое, что </?((?, = q' и а^) = [1].

Пусть Е1— условный установочный эксперимент. Максимальная из сумм длин слов, приписанных вершинам ветвей описанного дерева, представляющего эксперимент Е, ведущих от корня к листу называется длиной эксперимента. Длину эксперимента Е обозначим 1(E). Условным установочным экспериментом для автомата 21 называем условный установочный эксперимент для всего множества состояний автомата 21.

Минимальную из длин экспериментов для автомата 21 обозначим /(21). Если для автомата не существует ни одного условного установочного эксперимента, то полагаем /(21) = —1. Известно [1], что для приведенных автоматов такой эксперимент существует всегда.

Иногда вместо выражения условный установочный эксперимент будем сокращенно писать у.у.э.

Безусловным установочным экспериментом для множества S состояний автомата 21 называется слово о; G А*, такое, что для любых двух состояний автомата qi,q2 Е S выполнено: если t]j(qi,a) = ч/;^,а), то <p(qi,a) = Tp(q2,a). Слово а с указанным выше свойством называем также установочным для множества S автомата 21.

Безусловный установочный эксперимент для всего множества состояний автомата 21 называется безусловным установочным экспериментом для автомата 21. Установочное слово для всего множества состояний автомата 21 называется установочным для автомата 21.

Кратчайшую из длин установочных слов для автомата 21 обозначим /и(21). Если автомат 21 не имеет ни одного установочного слова, то полагаем lu(21) = —1. Известно [4], что если автомат является приведенным, то он имеет по крайней мере одно установочное слово.

Пусть К - некоторый класс автоматов. Обозначим 1(К) = тах1(ЩМК) = ™axlu(%).

Синхронизирующим словом для помножества Q\ С Q состояний автомата 21 называется слово о; такое, что Vgi, q2 G Qi Tp(q\, a) = y>(q2, or).

§2 Результаты работы.

Понятие условного и безусловного установочного эксперимента было введено Муром в [2]. В этой работе доказывается теорема о том, что если К® - класс всех приведенных автоматов с п состояниями, то 1(К®) < , Хиббард доказал, что для этого класса на самом деле имеет место равенство цКо) = -fi-a. и

Однако в примере Хиббарда, на котором достигается оценка , использовался входной алфавит с п — 1 символами и оставался открытым вопрос о том, какова оценка для длины установочного эксперимента в случае, если ограничить рост входного алфавита. В первой главе работы исследуется вопрос о зависимости длины условного установочного эксперимента от длины входного алфавита. Установлена возможность понижения оценки Мура-Хиббарда уже при п — 9 входных символах. Показано, что порядок этой оценки сохраняется вплоть до двухбуквенного входного алфавита. Отметим, что Карацуба рассматривал задачу получения оценок для функции 1(Кгде через К® обозначен класс всех приведенных автоматов Мура с п состояниями [3]. Он показал, что 1{К„) = (n-iKn-2) ^ j g ПрИмере автомата, на котором достигается нижняя оценка, используется входной алфавит из п — 1 символов. В работе показывается, что квадратичный порядок из оценки Карацубы сохраняется вплоть до двухбуквенного входного алфавита, в то же время с помощью развитой в главе 1 техники можно установить возможность понижения верхней оценки в классе автоматов Мура с менее, чем п — 9 входными символами.

С задачей построения установочного эксперимента тесно связана задача синхронизации [5]. Ее можно рассматривать как установочную в классе автоматов без выходов. Кроме того понятно, что и в случае автоматов с выходами возможность склеивать состояния в процессе эксперимента оказывает существенное влияние на его структуру и сложность.

Во второй главе исследуются вопросы нахождения длины кратчайшей синхронизирующей последовательности для различных подмножеств состояний автоматов в различных классах. Рассматриваются две основные задачи:

1) получение оценок шенноновского типа для длины синхронизирующего слова;

2) получение средней длины синхронизирующего слова для почти всех автоматов.

При фиксированном г получен порядок для длины кратчайшего синхронизирующего слова для г — элементных подмножеств в классе всех автоматов с п состояниями. Установлена асимптотика длины кратчайшего синхронизирующего слова для г — элементных подмножеств для почти всех автоматов с п состояниями при г < log2 log2 log2 п и п —> оо.

Саломаа [18] рассмотрел задачу синхронизации в классе автоматов над термами [1]. В работе рассмотрена задача о средней высоте синхронизирующего терма в автоматах над термами. Получена асимптотика длины кратчайшего синхронизирующего терма для г — элементных подмножеств для почти всех автоматов над термами с п состояниями при г < log2 Iog2 log2 п и n —> оо.

Отметим, что подобные задачи "усреднения"в дискретной математике рассматривались различными авторами. Так, например, в [12] рассматривается задача поиска усредненного значения веса автомата, в [7] — задача нахождения усредненного значения степени отличимости автомата. Однако, используемый в настоящей работе подход к решению задачи синхронизации имеет существенные отличия от походов указанных работ, продиктованные спецификой рассматриваемой задачи.

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

В четвертой главе рассматривается задача определения длины установочного эксперимента для частичных автоматов. Такая постановка задачи может возникать, например, когда некоторые переходы автомата являются запрещёнными в том смысле, что переход по ним может привести к неисправностям автомата. В этом случае в процессе проведения эксперимента допускается подавать лишь слова, которые не приводят к повреждениям автомата. При £ —> 0 получена асимптотика для длины условного установочного эксперимента для г — элементных подмножеств частичных автоматов, где п —число состояний автомата. При ^ < |(1 — б), 0 < б < 1 получен порядок длины условного установочного эксперимента для г — элементных подмножеств частичных автоматов. Получена верхняя оценка вида С log^ п для остаточной степени отличимости равномерно для почти всех частичных автоматов с п состояниями и к выходными символами при п —>• оо. Указанная оценка обобщает оценку сверху Бардзиня вида С logfc п для степени отличимости равномерно для почти всех обыкновенных автоматов [13].

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

Сформулируем формально основные результаты работы.

Отметим, что используемая в настоящем введении нумерация теорем не зависит от принятой в нашей работе поглавной нумерации теорем.

Основное внимание в первой главе уделяется вопросу о зависимости длины установочного эксперимента от числа входных символов. Обозначим через К^ п— класс всех приведенных автоматов с т входными символами и п состояниями, через класс всех приведенных автоматов Мура с т входными символами и п состояниями. Имеют место следующие теоремы:

Теорема 1. Если п > 10, т < п - 9, то 1(К^п) < - 1.

Теорема 2. /(Х2°)П) > f + п - 5 и 1(К'*п) > £ + п - 5.

Во второй главе рассматривается задача о синхронизирующем слове для состояний автомата. Пусть 2l=(A,Q,B,9C>, ф) - автомат и {gj, q2,., qr} - некоторое множество состояний 21. Если для некоторого слова а из А* выполнено p(qi,a) = Tp(q2, a) = . Tp(qr, a), то длину кратчайшего такого слова назовем временем склейки данных г состояний. Введем функцию T%(qi, q2,., qr) , равную 0, если состояния • — автомата 21 склеить нельзя, и равную времени склейки этих состояний в противном случае. Пару (21, {gi, q2,., qy}) назовем r-инициальным автоматом. Пусть Ш = (21, {qi,q2, ■ • -Яг}) — 1—инициальный автомат. Тогда положим Т(03) = Г«а(<71^25 • • ч<ЗУ)

Пусть Кт>п- класс всех автоматов с т входными символами и га состояниями и К^п - подкласс класса Кт>п такой, что для всякой пары gi, состояний автомата из Кт^п найдется о; £ А*, такое, что </?(<7i, а) = tp(q2, <*).

Введем в рассмотрение следующую функцию: lgl{% г) = max Щди q2,., qr)•

Qi,Q2,-,qr}QQ Теперь определим такие две функции: l„l(m,n,r)= max f0/(2l,r); l'gl(rn,n,r) = max l'gl(Vl, г). m.n

Теорема 3. Справедливы следующие утверждения:

1) если г > 2, т > 2 — фиксированы, то lgi(m, п, г) пг при га —> оо; п — 2г г-1

2)lgi(m,n,r) > (-—) при т>г, п>2г. г — 1

Теорема 4. Имеет место:

1) если т > 2, то lgi(m, га, 2) = п, 2) = если г > 2, т > 2 - фиксированы, то l'gi(m, га, г) х га2 при га оо.

Теорема 5. Длл почти каждого 2-инициального автономного автомата 03 выполнено Т(ЯЗ) < "y/ralog2ra rzpw га —> оо.

Теорема 6. Если т > 2 фиксировано и г < log2 log2 log2 га mo почти каждого г-инициального автомата 95 с т входными символами выполнено: Т(<В) ~ (г — 1)/одтга при га —> оо.

Теорема 6 следующим образом обобщается на случай автоматов над термами.

Напомним определение автоматов над термами. Нас интересуют только автоматы без выходов, поэтому дадим определение именно таких автоматов.

Пусть Q— конечное множество, к > 1 и для всех г таких, что 1 < i < к, /Г4 : Q х Q • • • х Q —> Q — некоторое отображение. Пара 21 = п

Q> {/Г> /г2» • • • > /&*}) называется конечным автоматом над термами без выходов, а отображения /Г4 называются входными отображениями.

С каждым отображением /Г4 : Q —> Q связан функциональный символ fp арности г,-. Эти символы играют роль букв входного алфавита в обычных автоматах. В дальнейшем, говоря о системе функциональных символов автомата, мы будем понимать систему всех функциональных символов, соответствующих входным отображениям автомата. Аналогом входного слова в случае автоматов над термами будет терм.

Дадим индуктивное определение терма над системой F функциональных символов fp,l < г < к арностей п, 7*2,., :

1) Функциональный символ fp есть терм для всех г G

2) Если для некоторого г, 1 < i < к, Т\, Тг,., Тг.— суть термы над системой F, то fp(Ti, Гг,., ТГ1)— терм над системой F;

3) Те и только те выражения являются термами над системой F, которые могут быть получены за конечное число шагов последовательным применением правил 1) и 2).

Пусть Т - терм над системой F функциональных символов некоторого автомата с множеством состояний Q. С каждым таким термом можно связать отображение <рт • Q -> Q следующим образом:

1) если Т = fp для некоторого г Е Е^ то (рт(я) = /f'Cg? Ъ - > • ->я) Для всех Ч п из Q;

2) если Т = f*.(Ti,T2,.,Ts) для некоторого г, то <pr(q) = fiSwM),<рт2(я),. • •, <pt.{q) для всех я из Q

Определим далее высоту h(T) терма Т над системой F :

1) если Т = fp для некоторого г € Ek, то h(T) = 1;

2) если высоты термов Т^Тг,. ,ГГ. определены и Г = /^(Т^Тг,., Tri) для некоторого г Е Ek, то /i(T) = max{h(Ti),., fo(Tr>.)} + 1.

Зафиксируем теперь г состояний <71,(72, .--,(7г некоторого автомата над термами 21 = (Q,F). Введем функцию времени склейки состояний <71, <72, • • • , qr следующим образом: если существует терм Т над системой F со свойством (pT(qi) = <Рт(я2) — • • * = tpriyr)), где отображение (рт определяется так, как указано выше по системе F, то минимальную из высот термов с таким свойством назовем временем склейки состояний в автомате 21 и обозначим T%(qi, (72,., qr). В противном случае положим (91» 02, .,gr) = 0.

Наконец, введем определение г — инициального автомата над термами. Пару (21, {<7i, <72, • • •, qr}), состоящую из автомата над термами 21 и неупорядоченного набора из г его состояний, назовем г— инициальным автоматом над термами. Пусть 03 = (21, {<7i,<72, • • • , (7r}) - f инициальный автомат над термами. Обозначим Т(03) = Ta(<7i, <72, •. •, qr)-Имеет место теорема:

Теорема 7. Если к, n, ri, г2,., 6 N, к > 1, R = тпах{г\, Г2,., т>}, R > 1 и г < log2 log2 log2 п, mo для почти всех г - инициальных автоматов 03 над термами с к входными отображениями арностей ri,r2, справедливо logi?log2(n) + С\ < Т(03) < logfllog2(n) + С2 при п —> оо, где С\, С>2— некоторые константы, эффективно определяемые по R.

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

Рассмотрим К^ к - класс всех приведенных автоматов с т входами, п состояниями и к выходами. Также рассмотрим класс К® - класс всех приведенных автоматов с п состояниями.

Пусть фиксирован автомат 21. Обозначим сг(21) = = таха(21).

Доказываются следующие две теоремы: Теорема 8. Имеет место j < сг(п) < га.

Теорема 9. Если т > 2, к > 2 фиксированы и п —> оо, то для любой константы С > 15, для почти всех автоматов 21 из Кт>П)к выполнено сг (21) < С.

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

Автомат 21 = (Л, Q, В, <р, ф) с частично определёнными функциями (р и ф называется частичным. Множество пар (q,a), для которых (риф определены, назовём множеством допустимых переходов и обозначим Av(21). Слово а длины г допустимо для q, если для всех i из ЕТ выполнено а1-1), а(г)) £ Av(21). Если G - граф переходов некоторого частичного автомата 21 = (A,Q, В,(р,ф), то такой граф будем называть автоматным и обозначать (A,Q,<p), а через ipo - функцию переходов соответствующего автомата. Множество пар (д, а), на которых не определены функции (риф, обозначим Av(21).

Рассмотрим множество Q' С Q. Слово а назовём частично разрешающим для множества Q\ если оно является допустимым для всех состояний множества Q' и либо найдутся два состояния q\ G Q' и <72 £ Q' такие, что а) = о;)) либо найдутся два состояния из множества Q' такие, что ф^1,а) ф ф^2,а). Для каждого подмножества Q' С Q обозначим через lp(Q') длину кратчайшего частично разрешающего слова для множества Q', если существует, по крайней мере, одно такое слово. В случае, когда для множества Q' не существует частично разрешающего слова, положим lp(Q') = — 1- Через Zp(2l, г) обозначим: max lv(Q'). Эту величину

Q'CQ,\Q'\=r назовём степенью частичной разрешимости автомата 21 порядка г.

Введём по аналогии понятие разрешимости автомата 21 = (А, Q, В, ср, ф) порядка г. Рассмотрим множество Q' С Q. Слово а назовём безусловным установочным экспериментом для множества Q', если оно является допустимым для всех состояний множества Q' и для любых двух состояний qi е Q' и q2 е Q' либо Tp(q\,a) = Tp(q2>a), либо i/>(qi,a) ф ф^2,а).

Для каждого подмножества Q' С Q обозначим через Q') длину кратчайшего безусловного установочного эксперимента для множества

Q', если существует, по крайней мере, один такой эксперимент. Здесь обозначение Р* выбрано для того, чтобы подчеркнуть, что речь идет о сложности экспериментов с частичными автоматами( от англ. partial). В случае, когда для множества Q' не существует ни одного безусловного установочного эксперимента, положим /^(21,(3') = —1.

Через 1%{%г) обозначим величину ^(21, г) = max

Q'QQ,\Q'\=r которую назовём степенью разрешимости автомата 21 порядка г. Нетрудно видеть, что при г = п степень разрешимости совпадает с длиной безусловного установочного эксперимента для автомата 21.

Введём понятие условной разрешимости автомата. Рассмотрим множество Qo С Q. Ориентированное от корня дерево Т назовём условным установочным экспериментом для множества состояний Qo автомата 21, если каждой вершине v приписано подмножество состояний Qv и слово av, а каждому ребру е — слово (Зе из выходного алфавита В таким образом, что выполняются следующие условия:

1) слово av является допустимым для всех вершин множества Qv;

2) если е = vv\ — ребро, выходящее из вершины v и Qe — {q 6 Qv : ip(q,av) = /?е}, то Qe ф 0 и QVl = lp(Qe,ocv) и, кроме того, для любого состояния q € Qv найдётся ребро е, выходящее из вершины v, такое, что 1>(q,<*v) = Ре',

3) Корню дерева приписано множество Qo)

4) Концевым вершинам дерева Т приписаны одноэлементные множества и пустые слова.

Если существует хотя бы один условный установочный эксперимент для множества состояний Qq автомата 21, то максимальную из сумм длин слов, приписанных вершинам ветвей, ведущих от корня к листьям таких деревьев, назовём длиной условного установочного эксперимента для множества Qo и обозначим 1рг(21, Qo) - В противном случае положим 1рг(21, Qo) = — 1. Наконец положим /рг(21, г) = max l^^Qo).

QoQQ,\Qo\=r

Обозначим через К класс всех частичных автоматов, у которых любые два состояния отличимы. Введём функции ^(n,r) и /рг(п, г, d, т) следующим образом: ^(n, г) = ^ max ^(21, г), lw(n,r,d,m) = max P"(5l,r).

A£K:\Q=n\,\AvC&)\=d,\A\=m

Зафиксируем автоматный граф G = (A, Q, ф) с |Q| = п и |Л| = т, где m > 2 и выходной алфавит В с \В\ = к, где к > 2. Множество всех частичных автоматов 05 = (Л, Q, В, </?, ф) с автоматным графом G обозначим S(G,k). Через S(G,k,r, R) обозначим подмножество множества S(G, к), состоящее из тех автоматов 05, для которых lp(*B,r) > R. Через S'(G, к, г, R) обозначим подмножество множества S(G, к), состоящее из тех автоматов 05, для которых /^"(05, г) > R.

Пусть R(n) : N —» N — монотонно возрастающая функция натурального аргумента. Скажем, что равномерно почти все частичные автоматы с т > 2 входными символами и к > 2 выходными символами имеют степень частичной разрешимости порядка г не больше R(n), если выполнено следующее предельное соотношение: max 0 при п оо.

Устанавливаются следующие результаты.

Теорема 10. Если т > 2 и к > 2, то найдутся константы С\ > 0 и Съ > 0 такие, что:

1) равномерно для почти всех частичных автоматов с т входными и к выходными символами степень частичной разрешимости порядка г не превосходит (С\г2 logj. п)г при п —У оо;

2) неверно, что равномерно для почти всех частично-определённых автоматов с т входными и к выходными символами степень частичной разрешимости порядка г не превосходит С2 log2 ^ при п —У оо.

Следствие 1. Если т > 2 и к > 2, то найдутся константы С\ > 0 и С2 > 0 такие, что:

1) равномерно почти все частичные автоматы с т входными символами и к выходными символами имеют степень частичной разрешимости порядка 2, не превосходящую С\ log2 п при п —> оо;

2) неверно, что равномерно почти все частично-определённые автоматы с т входными символами и к выходными символами имеют степень частичной разрешимости порядка 2, не превосходящую С2 log^ п при п —У оо.

Можно было бы предположить, что равномерно степень разрешимости не превосходит r(Cr2 log*. п)г, в частности, при г = 3 верхняя граница для равномерной оценки могла быть С log| п. Следующая теорема показывает, что указанное предположение неверно.

Теорема 11. Если т = 2,к = 2иг = 3, то для любого п > 4 существует такой автоматный граф Gen вершинами и т входными символами, что |s'(<j,fc,r,n-3)[ ^ 1 |S(G,fc)| - 8'

Теорема 12. Имеют место оценки: 1 )lpr(n,r)< £ С1п;

1 <i<r

2)1рг(п,г)>Сгпеслиг<1;

3) P"(n,r) > CI если г > f.

Доказываются следующие следствия из теоремы 12: Следствие 2.

Если r(n) : N —> N — монотонно возрастающая функция натурального аргумента и —> 0 при п —> оо, то lpr(п, r(n)) ~ Сп^ при п —> оо.

Следствие 3.

Если г(п) : N —> N — монотонно возрастающая функция натурального аргумента, Nq G N и при п > Nq выполнено — е, 0<е<|, то

1^(п,г{п)) х Сп^ при п —У оо.

Таким образом, при —> 0 полученная оценка асимптотически точна, при ^ — б, 0<б<| оценка точна по порядку.

В теореме 4 устанавливается, что в случае г = 2 порядок оценки из теоремы 12 сохраняется даже при одном запрете на функцию переходов и

3-х входных символах. 2

Теорема 13. Имеет место lpr(п, 2,1,3) >

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

Пусть дан приведенный автомат 21. Обозначим через h(21) степень отличимости автомата 21.

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

Введем понятие R2 - неполного автомата. Пусть дан автомат 21 = (A,Q, B,(p,tJj). Занумеруем его R\- компоненты числами от 1 до к. Таким образом, Q = (J Qi, где Qi - различные Ri компоненты автомата 21. Для каждого состояния q 6 Q определим отображение А —{1. к} следующим образом: fq(a) = г, если (p(q,a) £ Qi. Автомат назовем R2 - неполным, если найдется отображение / : А —> {1. к} такое, что / ф fq при q € Q.

Введем понятие класса автоматов-идентификаторов. Автомат 21 = (Л, Q, В, у?, -ф) назовем идентификатором, если найдутся состояние автомата 21, символы bo,bi из В и символ ао такие, что выполнено: 1) при q ф до из £ Q существует слово а из А* такое, что а) = qo;

2) при q ф qo любом а из А имеет место а) = &о;

3) ^{qo,a0) = h.

Для автомата 21 = (A,Q, В,(р,ф) обозначим if(2l,p) — класс автоматов 21' = (А, Q, В, <£>', таких, что существует не более р пар (q, а), для которых cp(q,a) ф <p'(q, а).

Также для автомата 21 = (A,Q, В,(р,ф) обозначим К'(21, р) следующий класс автоматов. В класс автоматов K'[pi,p) включаются все те и только те автоматы 21' = (А, -В', у?, f) с В С В\ для которых существует не более р пар (q, а) таких, что ^{q, а) ф ip'(q, а).

В следующих четырех определениях предполагается, что 21 — приведенный автомат. Обозначим htr($i,p) = min/i/m(03), где минимум берется по всем тем автоматам 03 из класса if (21,р), для которых существует у.у.э. Также обозначим Л/*г(21,р) = min/i(03), где минимум берется по всем приведенным автоматам 03 из класса К'($1,р).

Обозначим ltr($l,p) = min/(03), где минимум берется по всем тем автоматам 03 из класса К($1,р), для которых существует у.у.э. Также обозначим l'tr(Qi,p) = min£(03), где минимум берется по всем тем автоматам 03 из класса Х/(21,р), для которых существует у.у.э.

Рассмотрим функцию htr(n,m,p) = max/i*r(2l,p), где максимум берется в классе всех приведенных R2 — неполных автоматов с п состояниями и тп входными символами. Аналогично введем функцию h'tr(n,p) = max/i/fr(2l,p), где максимум берется в классе всех приведенных автоматов 21 с п состояниями.

Обозначим = maxfo<r(2l,p), где максимум берется по всем автоматам идентификаторам с п состояниями и аналогично Н'^(п,р) = max/i/<r(2l,p), где максимум берется по всем автоматам идентификаторам с п состояниями.

Обозначим теперь ltr(n,m,p) = max^r(2l,p), где максимум берется в классе всех приведенных R2- неполных автоматов с п состояниями и т входными символами. Также обозначим l^(n,p) = max/fr(2l,p), где максимум берется в классе всех автоматов-идентификаторов с п состояниями. Обозначим l'tr(n,p) = max//<r(2l,p), где максимум берется по всем приведенным автоматам с п состояниями. Наконец обозначим lfj(n,p) = max//tr(2l,p), где максимум берется в классе всех автоматов-идентификаторов с п состояниями.

Обозначим д(п,р) =]jgr[> 0i(n,p) = [^у].

Сформулируем теперь основные результаты пятой главы.

Теорема 14.

Существуют положительные константы С2 Е такие} что выполняются следующие неравенства:

1)^<^г(п>т>р)<С2шп1об?Р;

2)^» < /i/fr(n,p) < в"1^.

Теорема 15. Имеет место: д(п,р) ^ hlrd(n,p) ^ з(п,р) + 1; diP"! Р) ^ ^ + 1

Теорема 16. Существуют положительные константы С\,С2,Сз € М, такие, что выполняются следующие неравенства:

1) ltr(n,m,p) <

2) если р < то ltr(n,n,p) >

3)

4) ^(п.р) <

5) если р < §, то //fr(n,p) > Теорема 17. Имеет место: р+ l)si(n,p)(fl,(n,p) - 1)/2 ^ l*(n,p) s: min{ng(n,p),2^}, (р + lb(n,P)(fli(»,P) " 1)/2 ^ Г&(п,Р) < min{"<2"l<"'"»,

Основные результаты работы состоят в следующем:

1. Показано, что при п > 9 классическая оценка сложности условного установочного эксперимента "("-1) может быть понижена в классе автоматов с менее, чем п — 8 входными символами, где п— число состояний автомата. В то же время показано, что квадратичный порядок указанной оценки сохраняется при более чем однобуквенном входном алфавите.

2. Получена асимптотика длины кратчайшего синхронизирующего слова для г— элементных подмножеств для почти всех автоматов с п состояниями при г < log2log2log2ПИП4 оо.

3. Получен порядок для максимального значения отношения длин безусловного и условного установочного экспериментов. Получен порядок для значения отношения длин безусловного и условного установочного экспериментов для почти всех автоматов с п состояниями при п —> оо.

4. При ^ —> 0 получена асимптотика для длины условного установочного эксперимента для г— элементных подмножеств частичных автоматов, где п—число состояний автомата. При ^ < |(1 — б), 0 < е < 1 получен порядок длины условного установочного эксперимента для г— элементных подмножеств частичных автоматов.

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

Можно отметить следующие возможные направления для дальнейшего исследования:

1. Получение асимптотики для длины установочного эксперимента в классе автоматов с двумя входными символами.

2. Получение порядка и асимптотики для длины кратчайшего синхронизирующего слова для г— элементных подмножеств при растущем г.

3. Получение асимптотики или порядка для длины кратчайшего синхронизирующего слова для i— элементных подмножеств для почти всех автоматов с п состояниями при г > log2 log2 log2 пип-^оо.

4. Получение асимптотики или порядка для длины кратчайшего синхронизирующего терма для г— элементных подмножеств для почти всех автоматов над термами с п состояниями при г > log2 log2 log2 п и n —> оо.

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

6. Получение асимптотики для значения отношения длин безусловного и условного установочного экспериментов для почти всех автоматов с п состояниями при п —> оо.

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

8. Получение порядка и асимптотики для остаточной степени отличимости равномерно для почти всех частичных автоматов с п состояниями и к выходными символами при п —> оо, а также порядка и асимптотики для длины установочного эксперимента для почти всех частичных автоматов с п состояниями и к выходными символами при п —У оо.

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

Заключение.

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

2. Moore E.F. Gedanken-experiments on sequential machines, Automata Studies, 1956, 129-153русский перевод см. "Автоматы"(сб. статей), ИЛ, 19566 179-210]

3. Карацуба А.А. Решение одной задачи из теории конечных автоматов, 1960, УМН 15, т , 157-159.

4. Hibbard Т.Н. 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.]

5. D.Lee, М. Yannakakis Principles and methods of testing finite state machines, 1996, Proc of the IEEE, vol 84, 1090-1123.

6. Коршунов А.Д. О верхней оценке длин кратчайших однородных экспериментов по распознаванию заключительного состояния автомата для почти всех автоматов, 1969, ДАН СССР 184, №1, 28-29.

7. Коршунов А.Д. Об асимптотических оценках числа приведенных конечных автоматов, Дискретный анализ, 1966, вып. 6, 35-50.

8. Коршунов А.Д. О степени различимости конечных автоматов, Дискретный анализ, 1967, вып. 10, 39-57.

9. М.Н.Соколовский. Сложность порождения подстановок и эксперименты с автоматами, 1976, Сб. "Дискретный анализ", Вып. 29, Новосибирск, стр. 68-86.

10. Козловский В. А. О распознавании автомата относительно локально порожденного класса, 1981, Докл. АН СССР.- 258, 5. С. 1047 - 1049.

11. И.С. Грунский, В.А. Козловский, Г.Г. Пономаренко Представления конечных автоматов, 1990, Киев, Наукова думка.

12. Бардзинъ Я.М. О расшифровке автоматов, 1969, сб."Проблемы кибернетики", вып. 21, "Наука", 103-114.

13. Б.А Трахтенброт, Я.М Бардзинъ. Конечные автоматы (Поведение и Синтез), 1970,1. Москва. "Наука".

14. Василевский М.П. О расшифровке автоматов. "Кибернетика" 1974, №2, 18-23.

15. Феллер Вильям. Введение в теорию вероятностей и ее приложения, 1984, Москва. "Мир".

16. D. Eppstein Reset sequences for monotonic automata. SIAM J. on Computing, 1990, vol. 19, №, 500-510.

17. B. Ravikumar Implementing Sequential and Parallel Programs for the Homing Sequence Problem. Неопубликованный манускрипт. Интернет ссылка: http://citeseer.nj.nec.com/93406.html

18. A. Salomaa Synchronization of finite state automata. Contribution to an old problem, 2000, Turku Center For Computer Science Technical Report №365.

19. R.L. Rivest R.E. Shapire Inference of finite state automata using homing sequences, 1989, Proc 21st Annual ACM Symp. on Theory of Computing, 411-420.

20. A.T. Dabura, K. Sabnani, M.U. Uyar Formal methods for generating protocol conformace test sequnces, 1990, Proc. IEEE, vol. 78, №8.

21. К. Прахар Распределение простых чисел, изд-во "Мир",1967, Москва.

22. А.Е. Кирпасов О длине простого условного установочного эксперимента. Ж. Интеллектуальные системы, 2000, Т.5, вып. 1-4, 199-212.

23. А.Е. Кирнасов О склейке состояний автомата, Ж. Дискретная математика, 2003, №4, 66-83.

24. А.Е. Кирнасов О зависимости длины условного установочного эксперимента от локальных преобразований его диаграммы переходов и функции выходов . Ж. Дискретная математика, 2005, том 17, №2, 142-157.