О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова




НазваниеО задаче упорядочивания полугруппового автомата Светлана Александровна Акимова
Дата09.10.2012
Размер45.8 Kb.
ТипДокументы
О задаче упорядочивания полугруппового автомата

Светлана Александровна Акимова

Саратовский государственный социально-экономический университет, Саратов, Россия

Под упорядоченным автоматом будем понимать, следуя [1], алгебраическую систему вида , где  упорядоченное множество состояний автомата,  упорядоченное множество выходных сигналов,  полугруппа входных сигналов, функция переходов и  выходная функция, удовлетворяющие при всех условиям: и при фиксированном значении отображение является эндоморфизмом , отображение гомоморфизмом в .

Следует отметить, что автоматы, наделенные структурой упорядоченного множества, могут быть весьма эффективно использованы при решении широкого круга чисто прикладных задач. В частности, при моделировании работы автомата генетическими алгоритмами, при интеллектуальной обработке клавиатурных и других оракулов, при написании автоматных обработчиков для многообъектных программных комплексов и т.д. При этом структура упорядоченного множества может быть полезна как в процессе функционирования автомата, так и при интерпретации результатов его работы. Кроме того, она может быть использована для преобразования одного автомата в другой на этапе конструирования эффективного программного модуля. Важно также отметить, что при решении отдельных практических задач, в частности, задач интеллектуального моделирования, могут представлять интерес именно универсальные упорядоченные автоматы и эффективные способы их идентификации.

Заметим, что для автомата без равнодействующих входных сигналов каждый входной сигнал естественно отождествляется с парой отображений (где ). Значит, для такого автомата полугруппа входных сигналов может рассматриваться как полугруппа пар отображений (где , ) с операцией умножения . Более того, доказательство предложения 2.1 из [1] можно без труда перенести на следующий результат.

Лемма 1. Для произвольных упорядоченных множеств алгебраическая система с полугруппой и функциями , является упорядоченным автоматом, который обладает следующим универсальным свойством: для всякого упорядоченного автомата существует, и притом единственный, гомоморфизм по входным сигналам этого автомата в автомат .

Автомат называется универсальным упорядоченным автоматом над упорядоченными множествами .

В настоящей заметке для универсального упорядоченного автомата решена задача о конкретной характеристике [2]. Данную задачу можно сформулировать следующим образом: для автомата без равнодействующих входных сигналов требуется найти необходимые и достаточные условия, при которых множества и можно так упорядочить, что автомат будет совпадать с универсальным упорядоченным автоматом . Заметим, что конкретная характеристика универсальных упорядоченных полуавтоматов получена в работе [3].

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

Пусть  не пустые множества и  полугруппа пар отображений в и в с определенной выше операцией умножения.

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

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

Определим для полугруппы на множестве каноническое отношение по формуле:

.

Очевидно, что и  симметричные бинарные отношения.

Полугруппу будем называть -замкнутой, если для любой пары отображений (где ) из условия, что для любых , удовлетворяющих свойству , существует , для которого ограничение совпадает с ограничением и ограничение совпадает с ограничением , следует .

ТЕОРЕМА. Автомат без равнодействующих входных сигналов в том и только том случае совпадает с универсальным упорядоченным автоматом для некоторого нетривиального порядка на множестве и некоторого порядка на множестве , если полугруппа входных сигналов является  замкнутой полугруппой и ее канонические отношения удовлетворяют следующим схемам аксиом:

(А1) для любого выполняется (здесь );

(A2) для любых различных элементов и любых элементов , удовлетворяющих условию

,

выполняется (здесь );

(A3) если и элементы удовлетворяют условиям и

,

то

(здесь );

(A4) существуют такие различные элементы , что .

Таким образом, полученный результат дает алгоритм решения задачи о том, какой конечный автомат может быть упорядочен так, что будет универсальным упорядоченным автоматом. С другой стороны, этот результат можно применять в изучении абстрактных и элементарных свойств универсальных упорядоченных автоматов.

Список литературы


  1. Плоткин Б.И., Гринглаз Л.Я., Гварамия А.А. Элементы алгебраической теории автоматов. М.: Высш.шк., 1994.

  2. Улам С. Нерешенные математические задачи. М.: Наука, 1964.

  3. Акимова С.А. О характеризации упорядоченных автоматов // Социально-экономическое развитие России: Проблемы, поиски, решения: Сб. науч. тр.  Саратов: Изд. центр Сарат. госуд. соц.-эконом. ун-та, 2005. Ч. 2. С. 105-106.

Похожие:

О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconДни защиты от экологической опасности
Акимова, Т. А. Переход неизбежен : [гос экологич политика РФ и практика ее реализации] / Т. А. Акимова // Экология и жизнь. 2006....
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconБюллетень новых поступлений за 1 кв. 2012 года
Акимова, Ю. Ю. Использование рабского труда (уголовно-правовой аспект): Моногр./ Ю. Ю. Акимова. М.: Рап, 2011. 194 с
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconПамятка «Семь шагов к успеху»
Гоцул Светлана Александровна, учитель русского языка и литературы высшей квалификационной категории, моу сош №4, г. Ковров
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconОда теореме Пифагора
Руководитель кружка -учитель математики высшей категории, учитель-методист Барановская Светлана Александровна
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова icon«Нестандартные методы решения уравнений» Заяц Светлана Александровна
Решение некоторых уравнений сведением их к решению систем уравнений относительно новых неизвестных
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова icon1. Наименование дисциплины
Исследование характеристик конечных автоматов. Описание функционирования вероятностного конечного автомата, конечных автоматов Мили...
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconЛабораторная работа 16. Синтез микропрограммного автомата по блок-схеме алгоритма
Цель работы: Изучить способы синтеза микропрограммного автомата по блок-схеме алгоритма
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconПрограмма дополнительного образования для учащихся 7-12 лет Автор: Лапина Светлана Александровна, педагог дополнительного образования, руководитель фольклорного ансамбля «Подсолнух»
Содержание дополнительной образовательной программы. Учебно-тематический план 1 год обучения
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconАкимова Т. А. Экономика устойчивого развития: учеб пособие / Т. А. Акимова, Ю. Н. Мосейкин
Стратегия и проблемы устойчивого развития России в XXI веке / под ред. А. Г. Гранберга, В. И. Данилова-Данильяна, М. М. Циканова,...
О задаче упорядочивания полугруппового автомата Светлана Александровна Акимова iconАлександровна Подкорытова, психолог Мария Федоровна Попова, кандидат филологических наук, доцент Ургу екатеринбург Союз юных корреспондентов Свердловской области 2007
Светлана Дашиевна Балмаева, кандидат философских наук, декан факультета телерадиожурналистики Гуманитарного университета
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница