ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2011/2012, ТОМ 17, ВЫПУСК 7, СТР. 175-186
Б. Плоткин
Т. Плоткина
Аннотация
Посмотреть как HTML
Посмотреть как рисунок
В этой статье мы хотели бы вновь обратиться к основам треугольного произведения автоматов и ввести понятие сложности линейного автомата. Статья содержит три основных результата. 1. Для любых двух абстрактных автоматов мы рассмотрим категорию их каскадных соединений. Она содержит универсальный терминальный объект -- сплетение автоматов. Поэтому каждое каскадное соединение допускает естественное вложение в сплетение автоматов. 2. Аналогичная теория построена для линейных автоматов, для которых мы соответственно рассматриваем категорию каскадных соединений. Она также содержит терминальный объект, этот объект является треугольным произведением линейных автоматов. 3. Треугольное произведение имеет различные приложения. Эта конструкция используется в теории разложения линейных автоматов, в определении сложности линейного автомата. Мы определяем понятие сложности линейного автомата и даём правило для её подсчёта.
Полнотекстовая версия статьи в формате PDF (139 Kb)
| Главная страница | Содержание журнала | Новости | Поиск |
URL страницы: http://mech.math.msu.su/~fpm/rus/k1112/k117/k11710h.htm
Изменения вносились 24 мая 2013 г.