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

ВВЕДЕНИЕ

ТОПОЛОГИЧЕСКИЕ СВОЙСТВА ЭКСПЕРИМЕНТОВ С

АВТОМАТАМИ

1.1. Основные понятия и определения

1.2. Обобщенные контрольные эксперименты

1.3. Обобщенные распознающие эксперименты

1.4. Выводы

2. КЛАССЫ АВТОМАТОВ, ЗАДАННЫЕ ФИНИТНЫМИ

СРЕДСТВАМИ

2.1. Введение ^ ' й»' -ч

2.2. Основные понятия и определения

2.3. Алгебраическая структура множества финитно-определенных классов

2.4. Операторы алгебраического замыкания и аппроксимации

2.5. Выводы

3. ЭКСПЕРИМЕНТЫ В ФИНИТНО-ОПРЕДЕЛЕННЫХ КЛАССАХ 1-ГО РОДА

3.1. Основные понятия и определения

3.2. Топологические свойства финитно-определенных классов 1-го рода

3.3. Контрольные эксперименты в финитно-определенных классах 1-го рода

3.4. Распознающие эксперименты в финитно-определенных классах 1 -го рода

Актуальность темы.

Данная работа посвящена изучению одной из классических и актуальных проблем теории конечных автоматов - задаче сравнения поведения автоматов с помощью экспериментов. При этом под экспериментом [15,17,42] понимается процесс подачи входных слов на неизвестный автомат - "черный ящик", принадлежащий априорно заданному классу I*1, получение его реакций и вывод заключений о функциях автомата. Для конечных классов Р теория экспериментов разработана достаточно хорошо [4,12,13,14,42,48].

Для бесконечных классов Р изучение экспериментов находится в зачаточном состоянии. Принципиальными трудностями таких исследований являются отсутствие общих конструктивных средств представления априорных классов и общих алгоритмов вывода заключений. В последнее время в задачах контроля и диагностики дискретных устройств возникают потенциально бесконечные классы автоматов, задаваемые конечными средствами - спецификациями на заданное поведение. Другими источниками бесконечных классов заданных конечными средствами, являются задачи контроля протоколов сети ЭВМ, компонент сети автоматов и др. [5,24,25,35,36].

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

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

Диссертационная работа выполнена в соответствии с планами научно-исследовательских работ лаборатории прикладных проблем дискретной математики ИПММ HAH Украины (г. Донецк):

НИР 01900012554 - Представление конечных автоматов фрагментами поведения ( 1989 - 1993 )

НИР 0194U022564 - Исследование обратных задач теории автоматов применительно к идентификации и распознаванию дискретных систем ( 1994 - 1998 )

НИР - Исследование актуальных проблем моделирования, управления и идентификаций дискретных систем ( 1999 ).

Цель работы и задачи исследования.

Главная цель исследований состоит в:

- разработке подхода к изучению экспериментов с бесконечными классами автоматов на основе представления процесса вывода заключений как процесса анализа убывающей последовательности некоторых классов (окрестностей в метрических пространствах) автоматов безотносительно к способу подачи входных и наблюдения выходных слов при эксперименте с черным ящиком;

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

- построении методов проведения контрольных и распознающих экспериментов с финитно-определенными классами автоматов.

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

Научная новизна полученных результатов.

В работе введен и обоснован подход к исследованию контрольных и распознающих экспериментов на основе их представления сходящимися последовательностями окрестностей в метрических пространствах автоматов. Для произвольных автомата-эталона А, класса автоматов Р и метрики р найдены точные ( неконструктивные в общем случае ) критерии существования и получены нормальные формы контрольных и распознающих экспериментов. Для контрольных экспериментов этот критерий является новым, а для распознающих - обобщением критерия из [9].

Введено и обосновано задание потенциально бесконечного класса инициальных автоматов конечным слабоинициальным недетерминированным автоматом, обобщающее [35]. Рассмотрена совокупность всех таких классов. Показано, что она является дистрибутивной решеткой с нулем и единицей, но не булевой алгеброй.

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

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

Для специальной бэровской метрики (3 , отражающей близость автоматов по поведению, найдены конструктивные условия существования контрольного эксперимента относительно произвольных А и класса Е З^и^- Показано, что для любого такого Р всегда существует распознающий эксперимент относительно его подкласса, не содержащего предельных автоматов класса Р. Для случая Р У эт0 утверждение в общем случае не выполняется.

Найдены конструктивные критерии бесконечности, конечности и одноэлементности класса F Е |J $2 ? подкласса его предельных автоматов UmF и открывания ]F[= F — limF. Показана замкнутость относительно оператора lim.

Для бэровской метрики ß найден ряд конструктивных критериев существования контрольных экспериментов относительно класса G и автомата-эталона А, выбираемых из совокупности классов F, UmF и ]F[ для некоторого F Е Приведены оценки сложности таких экспериментов.

Показано, что существует разбиение {]UmkF[}k> 1 любого F G Уь где для каждого ]limkF[ есть распознающий эксперимент в бэровской метрике ß.

Для любого F е $2 найдена структура максимального по включению подкласса, для которого существует распознающий эксперимент в бэровской метрике ß.

Практическое значение полученных результатов.

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

Личный вклад соискателя.

Личный вклад соискателя состоит из : математической постановки задач контроля и распознавания автоматов в виде соответствующих задач в метрических пространствах автоматов; общих критериев существования контрольных и распознающих экспериментов и их частных случаев для #1. В статьях [18,19,20,21], опубликованных в соавторстве, личный вклад соискателя состоит в критериях существования и алгоритмах построения контрольных и распознающих экспериментов относительно Общее направление исследований принадлежит научному руководителю И. С. Грунскому.

Апробация результатов диссертации.

Основные положения и результаты работы докладывались и обсуждались на 3-й Международной конференции "Дискретные модели в теории управляющих систем" (Красновидово,1998), 12-й Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород,1999), областном семинаре "Актуальные проблемы компьютерных наук" (Донецк,1999), научных семинарах "Дискретные системы и формальные языки" (ИПММ HAH Украины,Донецк) и семинарах кафедры Компьютерных технологий (ДонГУ,Донецк).

Публикации.

Публикации по теме диссертации составляют три статьи [18,19,39] в журналах, одну в сборнике научных трудов [38], один препринт [21] и 2 тезиса докладов на международных конференциях [20,37].

Структура и объем работы.

Диссертация содержит 130 машинописных страниц и состоит из введения, четырех основных разделов, заключения и списка литературы из 55 источников.

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

1. Создан метод исследования контрольных и распознающих экспериментов на основе их представления сходящимися множествами окрестностей в метрических пространствах автоматов. Для произвольных автомата-эталона А, класса автоматов F и метрики р найдены точные (неконструктивные в общем случае) критерии существования и нормальные формы контрольных и распознающих экспериментов.

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

3. Впервые введено финитное задание класса с помощью конечного множества маркеров. Показано, что совокупность $2 всех таких классов является булевой алгеброй.

4. Введены операторы аппроксимации 0р , ставящие в соответствие каждому классу автоматов F другой класс G Е , F С G. Показано, что эти операторы относительно выбранного класса автоматов F образуют дистрибутивную решетку. В терминах операторов найден критерий существования контрольного эксперимента относительно произвольных автомата А , класса F и метрики р.

5. Для бэровской метрики ß найдены конструктивные условия существования контрольного эксперимента относительно произвольных А и класса F Е Показано, что для открывания любого такого F всегда существует распознающий эксперимент.

6. Найдены конструктивные критерии конечности F Е SiU^j подкласса его предельных автоматов UmF и открывания Показана замкнутость относительно оператора lim.

7. Для бэровской метрики ß найдены конструктивные критерии существования контрольных экспериментов относительно класса G и автомата-эталона А, выбираемых из множества классов F, UmF и ]F[ для некоторого F Е (J • Приведены оценки сложности таких экспериментов.

8. Показано, что существует разбиение вида {]ИткР[}к>1 любого Р 6 Зъ где каждый }ИткР[ является финитно-распознаваемым классом.

9. Для любого найдена структура максимального по включению финитно-распознаваемого подкласса.

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

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

ЗАКЛЮЧЕНИЕ

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

1. Архангельский A.B., Пономарев В.И. Основы общей топологии в задачах и упражнениях.- М.: Наука, 1974.-424 с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.- 536с.

3. Барашко A.C., Скобцов Ю.А., Сперанский Д.В. Моделирование и тестирование дискретных устройств.- АН Украины. ИПММ.-Киев: Наукова думка, 1992.-288с.

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

5. Барздинь Я.М. О расшифровке автоматов при отсутствии верхней оценки числа состояний // Докл. АН СССР. 1970.- 190, N 5.-С.1048-1051.

6. Богомолов A.M., Барашко A.C., Грунский И.С. Эксперименты с автоматами.- Киев: Наукова думка, 1973.- 144с.

7. Богомолов A.M., Грунский И.С., Сперанский Д.В. Контроль и преобразование дискретных автоматов.- Киев: Наукова думка, 1975.-176с.

8. Бородай С.Ю. Условные и безусловные эксперименты с классами реализаций НД-автоматов // Тезисы докладов на XI Международной конференции по проблемам теор. кибернетики / Под редакцией С.В.Яблонского, Ульяновск: изд. СВНЦ:, 1996.- С.27-28.

9. Бородай С.Ю. Эксперименты в эффективно заданных классах автоматов: Дисс. канд.физ.-мат.наук; 01.01.09/ СГУ.- Саратов, 1997.

10. Брауэр Р. Введение в теорию конечных автоматов,- М.: Радио и связь, 1987.- 392с.

11. Бурбаки Н. Общая топология. Основные структуры.- М.: Физматгиз, 1958.

12. Василевский М.П. О распознавании неисправностей автомата

13. Кибернетика.- 1973.- N 4.- С.93-108.

14. Василевский М.П. О расшифровке автоматов // Кибернетика.-1974.- N 2.- С.19-23.

15. Гилл А. Введение в теорию конечных автоматов. М.:Наука, 1966.- 272с.

16. Глушков В.М. Синтез цифровых автоматов.- М.: Физматгиз, 1962.- 476с.

17. Грунекий И.С. Контроль и диагностика автоматов с идентификаторами состояний // Тр. симпоз. ИФАК "Дискретные системы".-Рига:3инатне, 1974.-Т.4.-С.82-89.

18. Грунский И.С., Козловский В.А., Пономаренко Г.Г. Представления конечных автоматов фрагментами поведения.- Киев: Наукова думка, 1990.- 232с.

19. Грунский И.С., Максименко И.И. Об экспериментах с автоматами при отсутствии верхней оценки числа состояний // Докл. НАНУ.- 1996.- N 6.- С.31-35.

20. Грунский И.С., Максименко И.И. Об экспериментах с автоматами при отсутствии верхней оценки числа состояний // Кибернетика и системный анализ. 1999.- N 4.-С.59-71.

21. Грунский И.С., Максименко И.И. О распознавании детерминированных автоматов из классов, заданных недетерминированными автоматами // Тр. III Межд. конф. "Дискретные модели в теории управляющих систем", Красновидово'98.- М.: Диалог МГУ, 1998.-С.25-29.

22. Грунский И.С., Максименко И.И. Эксперименты с маркированными автоматами. Препринт N 96.02. HAH Украины, ИПММ.-Донецк, 1998. 33 с.

23. Грунский И.С., Петренко А.Ф. Построение проверяющих экспериментов с автоматами, описывающими протоколы // Автоматикаи вычислительная техника.-1988.-N 4.-С.7-14.

24. Данеев A.B., Русанов В.А. К аксиоматической теории идентификации динамических систем // Автоматика и телемеханика. -1994. N 8.-С.126-135.

25. Евтушенко Н.В., Матросова А.Ю. К синтезу контролепри-годных автоматных сетей // Техническая диагностика.- 1991.- N 3.-С.143-152.

26. Евтушенко Н.В., Петренко А.Ф. Метод построения проверяющих экспериментов для произвольного детерминированного автомата // Автоматика и вычислительная техника.- 1990.- N 5.- С.73-76.

27. Евтушенко Н.В., Петренко А.Ф. О проверяющих возможностях кратных экспериментов // Автоматика и вычислительная техника.-1989.- N 3.- С.9-14.

28. Капитонова Ю.В., Летичевский A.A. Математическая теория проектирования вычислительных систем.- М.: Наука, 1988.- 296с.

29. Катленд П. Вычислимость. Введение в теорию рекурсивных функций : Пер. с англ. М.:Мир,1983.-256 с.

30. Келли Дж. Общая топология: Пер. с англ.-20е изд.-М.: Наука, 1981.-432 с.

31. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1968.-496 с.

32. Кон П. Универсальная алгебра.- М.: Мир, 1968.- 352 с.

33. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. М.: Наука, 1985.- 320с.

34. Кузнецов A.B., Трахтенброт Б.А. Исследование частично-рекурсивных операторов средствами теории бэровского пространства // ДАН СССР 105, N 5.-1955.-С. 897-900.

35. Кушнир Б.А. Лекции по конструктивному математическому анализу М.: Наука, 1973.-448 с.

36. Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов// Кибернетика и системный анализ.-1996.-К 4.-е.34-50.

37. Лукьянов Б.Д. О различающих и контрольных экспериментах с недетерминированными автоматами // Кибернетика и системный анализ.-1995.-N 5.-с.56-66.

38. Максименко И.И. Распознавание в финитно определенных классах // Тезисы докладов XII Международной конференции (Нижний Новгород, 17-22 мая 1999 г.) Часть II -М.: Изд-во мехмата МГУ, 1999.-С.143.

39. Максименко И.И. Распознавание в эффективно заданных классах автоматов// Труды ИПММ HAH Украины.-Донецк,1998.-С.115~ 123.

40. Максименко И.И. Эксперименты в классе реализаций недетерминированных автоматов // Доклады HAH Украины.-1999.-N 7.-С.95-99.

41. Мальцев А.И. Алгоритмы и рекурсивные функции.-М.: Наука, 1965.- 391с.

42. Мартин-Леф П.Очерки по конструктивной математике.-М.: Мир,1975.-136с.

43. Мур Э.Ф. Умозрительные эксперименты с последовательност-ными машинами // Сб.: Автоматы.- М.: ИЛ, 1956.- С.179-210.

44. Основы технической диагностики/Под ред. П.П.Пархоменко.-М.:Энергия, 1976.- 464с.

45. Петер Р. Рекурсивные функции.- М.: Иностриздат, 1954.-264с.

46. Рудин У. Основы математического анализа.-М.:Мир,1966.

47. Строгалов A.C. Об е -моделировании поведения конечных автоматов: Дисс. канд.физ.-мат.наук; 01.01.09/ СГУ.- Саратов, 1985.

48. Твердохлебов В.А. Логические эксперименты с автоматами.-Саратов.: Изд-во Саратовского университета,1988.- 184с.

49. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтез). М.: Наука, 1970.- 400 с.

50. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения.-М.: Наука. Гл.ред.физ.-мат.лит.,1987. -288 с.

51. Харари Ф. Теория графов.- М.: Мир, 1973.- 300с.

52. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств.-М.:Наука.Гл.ред.физ.-мат.лит., 1980.-400 с.

53. Яблонский С.В. Введение в дискретную математику.- М.:Нау-ка,1997.- 384с.

54. Boroday S.U. Distinguishing tests for nondeterministic finite state machines // Proceedings of the IFIP TC6 11th IWTCS'98 (Tomsk 98) Kluver Acad. Publ. 1998, p. 101-108.

55. Grunsky I. Testing of automata: from experiments to representations by meaus of fragments // Testing of Communicating System. Proc of the IFIP TC6 11th IWTCS' 98 Kluver Acad.Publ, 1998.- p.3-14.

56. Hennie F.C. Fault detecting experiments for sequential circuits // Proc.5th Ann.Symp."Switch Circuit Theory and Logic. Design".- 1964.-P.95-110.