Каскадное соединение и треугольное произведение линейных автоматов

В этой статье мы хотели бы вновь обратиться к основам треугольного произведения автоматов и ввести понятие сложности линейного автомата. Статья содержит три основных результата. 1. Для любых двух абстрактных автоматов мы рассмотрим категорию их каскадных соединений. Она содержит универсальный терминальный объект – сплетение автоматов. Поэтому каждое каскадное соединение допускает естественное вложение в сплетение автоматов. 2. Аналогичная теория построена для линейных автоматов, для которых мы соответственно рассматриваем категорию каскадных соединений. Она также содержит терминальный объект, этот объект является треугольным произведением линейных автоматов. 3. Треугольное произведение имеет различные приложения. Эта конструкция используется в теории разложения линейных автоматов, в определении сложности линейного автомата. Мы определяем понятие сложности линейного автомата и даём правило для её подсчёта.