Универсальная алгебра и автоматы

Description

Учебное пособие, 1988 г., 73 стр. Саратовский государственный университет. ISBN 5-292-00263-1В пособии излагаются основные понятия и результаты теории конечных автоматов без выхода, связанные с универсально-алгебраическими конструкциями. Представление об автомате без выхода как о конечной унарной алгебре позволяет применить в теории автоматов хорошо разработанные универсально-алгебраические средства, придать установленным с их помощью фактам естественную "автоматную" трактовку. Для студентов механико-математических факультетов университетов, а также для всех занимающихся или интересующихся алгебраической теорией автоматов.Содержание:Абстрактные автоматы и способы их задания.Решетка подавтоматов автомата. Упорядоченные множества и решетки. Некоторые свойства решетки подавтоматов. Конечные дистрибутивные решетки как решетки подавтоматов.Решетка конгруэнций автомата. Эквивалентности и разбиения. Конгруэнции автомата. Алгоритм построения решетки конгруэнций автомата. Автоматы со специальными типами решетки конгруэнций. Конечные решетки как решетки конгруэнций автоматов. Конгруэнции и разложение автоматов.Моноид эндоморфизмов и группа автоморфизмов автомата. Гомоморфизмы и конгруэнции автомата. Моноиды и преобразования. Некоторые свойства моноида эндоморфизмов автомата. Некоторые свойства группы автоморфизмов автомата. Гомоморфизмы автоматов как матрицы.Литература.