толерантный образ

МОРФИЗМЫ ПО СТАБИЛЬНЫМ ТОЛЕРАНТНОСТЯМ КОНЕЧНЫХ АВТОМАТОВ

В работе предлагается метод построения по некоторой тройке толерантностей на множествах состояний, входных и выходных символов конечного детерминированного автомата другого автомата, связанного определенным морфизмом с исходным. Рассматриваемые построения обобщают известный метод нахождения гомоморфных образов автомата по тройке эквивалентностей, удовлетворяющей определенным условиям.

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

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