Образец для цитирования:

Мангушева И. П. Упорядоченные автоматы и толерантные образы КДА // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 91-99. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-1-91-99

Язык публикации:

русский

Рубрика:

Информатика

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

Авторы:

Мангушева Ирина Павловна, ФГБОУ ВПО Саратовский государственный университет имени Н.Г. Чернышевского, Россия, г. Саратов, ул. Астраханская, 83 , MangushevaIP@info.sgu.ru

Аннотация:

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

Ключевые слова:

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

DOI:

https://doi.org/10.18500/1816-9791-2013-13-2-1-91-99

Библиографический список

1. Мангушева И. П. Морфизмы по стабильным толе-

рантностям конечных автоматов // Изв. Сарат. ун-та.

Нов. сер. Сер. Математика. Механика. Информатика.

2008. Т. 8, вып. 4. С. 80–90.

2. Богомолов А. М., Салий В. Н. Алгебраические осно-

вы теории дискретных систем. М. : Наука, 1997. 368 с.

3. Карпов Ю. Г. Теория автоматов. СПб. : Питер, 2003.