birmaga.ru
добавить свой файл

1
ВЗАИМОСВЯЗЬ СВОЙСТВ


УНИВЕРСАЛЬНЫХ УПОРЯДОЧЕННЫХ ПОЛУАВТОМАТОВ И ПОЛУГРУПП ИХ ВХОДНЫХ СИГНАЛОВ

С.А. Акимова

СГСЭУ, Саратов, Россия

В настоящей заметке построена относительно элементарная интерпретация класса универсальных упорядоченных полуавтоматов [4] в классе всех полугрупп с целью последовательного изучения свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов.

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


  1. множество не пусто;

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


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

С помощью этого результата исследованы задачи о том, как универсальные упорядоченные полуавтоматы определяются своими полугруппами входных сигналов, которые непосредственно связаны с известными результатами Л.М.Глускина [2] и Ю.М.Важенина [1].

Теорема 2. Пусть упорядоченные множества, причем порядок на одном из множеств отличен от тождественного. Тогда для универсальных упорядоченных полуавтоматов следующие условия эквивалентны:


  1. полугруппы входных сигналов полуавтоматов элементарно эквивалентны;

  2. полуавтомат элементарно эквивалентен полуавтомату или двойственному для него полуавтомату .

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

Теорема 3. Для любого класса K универсальных нетривиально упорядоченных полуавтоматов справедливы следующие утверждения:

  1. если элементарная теория класса K наследственно неразрешима, то и элементарная теория класса полугрупп наследственно неразрешима;

  2. если элементарная теория класса K эффективно неотделима, то и элементарная теория класса полугрупп эффективно неотделима.

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


  1. Важенин Ю.М. Элементарные свойстваполугрупп преобразований упорядоченных множеств // Алгебра и логика. 1970. Вып. 9, №3. С.281-301.

  2. Глускин Л.М. Полугруппы изотонных преобразований // УМН. 1961. Т.16, №5. С. 157-162.

  3. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М.:Наука, 1980.

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