RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика // Архив

Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 2013, том 13, выпуск 2(1), страницы 91–99 (Mi isu401)

Информатика

Упорядоченные автоматы и толерантные образы КДА

И. П. Мангушева

Кафедра дискретной математики и информационных технологий, Саратовский государственный университет им. Н. Г. Чернышевского

Аннотация: Рассматривается конечный детерминированный автомат (КДА), множества состояний, входных и выходных символов которого частично упорядочены (упорядоченный автомат). Определяется отображение КДА на упорядоченный автомат, названное $p$-морфизмом. Показано что так называемые толерантные образы, построенные по отношениям стабильной толерантности на множестве состояний КДА, являются частным случаем упорядоченных автоматов, связанных с исходным $p$-морфизмом. Определяются необходимые и достаточные условия, при которых упорядоченный автомат является толерантным образом заданного автомата.

Ключевые слова: конечный детерминированный автомат, толерантный образ, упорядоченный автомат, стабильная толерантность, покрытие, частичный порядок.

УДК: 519.95

DOI: 10.18500/1816-9791-2013-13-2-1-91-99



Реферативные базы данных:


© МИАН, 2024