|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Анализ поведения автоматов
В. Б. Кудрявцев, И. С. Грунский, В. А. Козловский
Аннотация:
Обзор содержит результаты, относящиеся к поведенческой и абстрактной теории конечных автоматов. Классическими задачами этой теории являются прямые задачи: задачи анализа процессов преобразования информации, осуществляемых автоматами, и свойств автоматов, и обратные задачи: задачи синтеза автоматов с заданными свойствами и идентификации (восстановления, распознавания, расшифровки, контроля и диагностики) автомата путем экспериментов с ним.
Задача синтеза состоит в построении автомата по заданной его спецификации – заданию на необходимое, возможное и запрещенное поведение, а задача идентификации – в построении автомата с помощью проведения экспериментов с заданным “черным ящиком” – реализацией этого автомата. В процессе эксперимента возникает фрагмент поведения автомата. Поэтому имеется единая исходная основа – фрагмент поведения для решения задач анализа свойств автомата по его поведению и синтеза автомата, удовлетворяющего заданному поведению с некоторой точностью. Эти задачи и рассматриваются в обзоре.
В последние десятилетия активно развиваются два научных направления, это формальные методы синтеза программно-аппаратных вычислительных систем и теория экспериментов с автоматами. Основная задача теории экспериментов состоит в разработке эффективных экспериментов, позволяющих получить (распознать) определенные сведения о строении автомата, его функциях, о характеристиках процесса преобразования информации, осуществляемого этим автоматом. При этом возникает большой круг задач, связанных с классификацией экспериментов, с вопросами разрешимости задач распознавания тех или иных свойств автомата определенными видами экспериментов, с оценками сложности минимальных экспериментов, достаточных для решения тех или иных задач распознавания, а также с оценками сложности построения этих экспериментов. Теория экспериментов интенсивно разрабатывается, в ней получен ряд важных и принципиальных результатов.
Предлагаемый обзор содержит ряд окончательных результатов, однако они являются лишь очередным шагом в исследовании задач анализа и синтеза автоматов по их поведению, которые постоянно наполняются новым содержанием и требуют дополнительных усилий и средств их разрешения.
Статья поступила: 20.06.2008
Образец цитирования:
В. Б. Кудрявцев, И. С. Грунский, В. А. Козловский, “Анализ поведения автоматов”, Дискрет. матем., 21:1 (2009), 3–35; Discrete Math. Appl., 19:1 (2009), 1–35
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1036https://doi.org/10.4213/dm1036 https://www.mathnet.ru/rus/dm/v21/i1/p3
|
Статистика просмотров: |
Страница аннотации: | 1390 | PDF полного текста: | 862 | Список литературы: | 89 | Первая страница: | 48 |
|