Семинар лаборатории ПОИС: Проблема эквивалентности для конечных автоматов-преобразователей над полугруппами // В.А. Захаров

На очередном заседании нашего семинара выступил ведущий научный сотрудник лаборатории Захаров Владимир Анатольевич. Тема его доклада: Проблема эквивалентности для конечных автоматов-преобразователей над полугруппами.

Аннотация. Автоматы-преобразователи (transducers) - это простейшая модель вычислений, которая позволяет описывать процессы преобразования конечных строк (текстов, изображений, потоков данных и др.) в оперативном режиме с использованием ограниченного объема памяти. В том случае, если выходные строки рассматривать как полугрупповые выражения, то автоматы-преобразователи могут служить моделью последовательных реагирующих программ. Для проверки правильности поведения таких моделей целесообразно использовать алгоритмы проверки их эквивалентности. В докладе будет рассказано об общем подходе к построению алгоритмов проверки эквивалентности конечных автоматов-преобразователей над полугруппами.