Введение к работе
Актуальность хамы. Интенсивное развитие различных аспектов теории математических моделей конечно-автоматного типа, продолжающееся уже несколько десятилетий и нашедшее отражение в целом ряде монографий (Айзерман М.А. и др., Бухараев Р.Г., Глушков В.М., Кудрявцев В.Б. и др., Трахтенброт Б.А. и Бардзинь Я.М., Чирков М.К., Яблонский СВ., Ginzburg A., Kan-dell А. и Lee S.C., Paz A., Salomaa A., Starke Р.Н. и другие), обусловлено как чисто теоретическим интересом к решению новых математических задач дискретной математики, так и с тем, что конечные автоматы различного вида являются в ряде случаев весьма удобной математической моделью для описания определенного класса систем, устройств, процессов и явлений. Существенное место среди таких моделей занимают различные виды обобщенных и стохастических (вероятностных) автоматов, которые изучали Бухараез Р.Г., Варшавский В.И., Мучник А.А., Хунядвари Л., Чирков М.К., Шестаков А.А., Carlyle J.W., Chimel К., Ginzburg A., Kandel A., Lee S.C., Paz A., Salomaa A., Starke Р.Н., Topencharov V.V., Turakiinen P., Wechler W., Dimitrov V. и многие другие. В том числе, понятие стохастического автомата широко используется в качестве математической модели целого ряда таких систем, устройств, процессов и явлений, которые содержат в себе элементы случайности (или, являясь по-существу детерминированными, подвергаются случайным воздействиям и т.п.) и допускают конечно-автоматную интерпретацию.
Одной из наиболее актуальных классических задач оптимизации математических моделей конечно-автоматного типа является проблема минимизации числа состояний автомата и построения его приведенных (или минимальных) форм. В том числе задача минимизации стохастического автомата рассматривалась в целом ряде работ (Бухараев Р.Г., Буй Мин Чи, Лазарев З.Г., Чен-цов В.М., Чирков М.К., Bacon G.C., Carlyle J.W., Even S., Paz A., Starke Р.Н. и др.) и были разработаны основы соответствующих методов, применимых именно к стохастическим автоматам, но часто содержащих довольно сложные для реализации на практике процедуры даже для систем с относительно небольшим чи-
.3
слом состояний, входов и выходов. В то же время в последние годы для качественно более общего случая обобщенных автоматов над некоторыми алгебраическими структурами (в том числе, над произвольными полями) М.К.Чирковым и А.А.Шестаковьш были обоснованы и разработаны аффективные матричные методы минимизации, которые, однако, напрямую неприменимы к стохастическим автоматам, так как могут нарушить корректность их задания. Поэтому представляется весьма актуальным рассмотреть такую модификацию общего матричного метода, которая бы при применении к стохастическому автомату не нарушала бы его стохастичности.
Цель работы. Основная цель данной работы - исследовать новые способы решения одной из классических задач оптимизации стохастических конечно-автоматных моделей - минимизации стохастических конечных автоматов и построения их стохастических и нестохастических минимальных форм (под нестохастическими минимальными формами стохастического автомата понимаются обобщенные автоматы над полем вещественных чисел, имеющие наименьшее число состояний и эквивалентные в определенном смысле втому стохастическому автомату), изучить вопрос об относительной сложности представления стохастических автоматов стохастическими и нестохастическими минимальными формами, разработать методику и алгоритмы построения минимальных форм стохастических автоматов, удобные для практической реализации на ЭВМ, и создать на их основе программу для оптимизации стохастических автоматов.
Методика исследования базируется на использовании аппарата математической теории автоматов, линейной алгебры и теории матриц, выпуклого анализа.
Научная новизна работы состоит в дальнейшем развитии некоторых результатов теории стохастических автоматов я обобщенных автоматов над произвольными нолями и доказательстве на этой основе ряда важных теоретических положений, позволивших теоретически обосновать и разработать новые, более эффективные методы оптимизации этих автоматов.
Практическая ценность работы заключается в создании на
основе ее теоретических результатов комплекса алгоритмов и программы для ПЭВМ IBM PC/AT, реализующих новый матричный метод построения минимальных форм стохастических автоматов, которые могут использоваться для практической оптимизации стохастических конечно-автоматных моделей.
Аппробацяя работы. Основные результаты диссертации были опубликованы в работах [1,2,3], представлены на Третьем международном совещании по модельно-ориентированвому анализу данных, докладывались и обсуждались на семинарах лаборатории математических проблем информатики НИИММ СПбГУ и кафедры статистического моделирования СПбГУ.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложения. Основной текст диссертации занимает 127стравиц машинописного текста. Библиография содержит 53 наименования. Приложение содержит 32 страницы.