Preview

Чебышевский сборник

Расширенный поиск

Об абстрактной определяемости универсальных гиперграфических автоматов полугруппами входных сигналов

https://doi.org/10.22405/2226-8383-2019-20-2-259-272

Полный текст:

Аннотация

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов называются универсальными гиперграфическими автоматами. Для таких автоматов полугруппы входных символов являются производными алгебрами отображений, свойства которых взаимосвязаны со свойствами алгебраических структур данных автоматов. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В работе исследуется проблема абстрактной определяемости таких автоматов их полугруппами входных символов, суть которой заключается в нахождении условий изоморфности полугрупп входных символов универсальных гиперграфических автоматов. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами с p−определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными), а также автоматы, у которых множества состояний и выходных символов разбиваются на классы некоторой эквивалентности без одноэлементных классов. В настоящей работе доказано, что универсальные гиперграфические автоматы над эффективными гиперграфами с p−определимыми ребрами полностью (с точностью до изоморфизма) определяются своими полугруппами входных символов, а также описано строение измоморфизмов таких автоматов.

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

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

2. Molchanov V. A. Semigroups of mappings on graphs // Semigroup Forum. 1983. № 27. P. 155–199.

3. Свердловская тетрадь: Сборник нерешенных проблем теории полугрупп. Свердловск: Урал. гос. ун-т, 1979. 41 с.

4. Лендер В. Б. Об эндоморфизмах проективных геометрий // Исследования алгебраических систем (Матем.записки Урал. ун-та). 1984. С. 48–50.

5. Молчанов В. А. Как проективные плоскости определяются своими полугруппами // Теория полугрупп и ее приложения. Полугруппы и связанные с ними алгебраические системы, Саратов. гос. ун-т. 1984. C. 42–50.

6. Molchanov V. A universal planar automaton is determined by its semigroup of input symbols // Semigroup Forum. 2011. № 82. P.1–9.

7. Bretto A. Hypergraph theory. An Introduction. Cham: Springer, 2013. 133 p. DOI: 10.1007/978-3-319-00080-0.

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

9. Молчанов В. А., Хворостухина Е. В. О задаче абстрактной характеризации универсальных гиперграфических автоматов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. - Саратов: Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского, 2017. Т. 17, № 2. C. 148–159.

10. Молчанов В. А., Хворостухина Е. В. Об абстрактной определяемости универсальных гиперграфических автоматов полугруппами их входных сигналов // Материалы XIV Международной конференции .Алгебра и теория чисел: современные проблемы и приложения., посвященная 70-ти летию со дня рождения С. М. Воронина и Г. И. Архипова. – Саратов: Изд-во Саратовского гос. ун-та, Издательский центр .Наука., 2016. С. 67–69.

11. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. М. : Мир, 1972. Т. 1. 286 с.

12. Вагнер В. В. Теория отношений и алгебра частичных отображений // Теория полугрупп и ее приложения; Сб. научн. тр. 1965. № 1. С. 3–178.

13. Молчанов А. В. Полугруппы эндоморфизмов слабых p−гиперграфов // Известия вузов. Математика. Саратов. 2000. № 3(454). С. 80–83.

14. Molchanov A. V. On definability of hypergraphs by their semigroups of homomorphisms // Semigroup Forum. 2001. № 62. P. 53–65.

15. Молчанов А. В. Об определяемости гиперграфических автоматов их выходными функциями // Теоретические проблемы информатики и ее приложений. Саратов. 1998. № 2. С. 74–84.

16. Хартсхорн Р. Основы проективной геометрии. М.: Мир, 1970. 161 с.

17. Хворостухина Е. В. Об одном классе гиперграфических автоматов // Теорет. проблемы информатики и ее приложений. Саратов. 2008. № 8. С. 112–118.


Для цитирования:


Молчанов В.А., Хворостухина Е.В. Об абстрактной определяемости универсальных гиперграфических автоматов полугруппами входных сигналов. Чебышевский сборник. 2019;20(2):259-272. https://doi.org/10.22405/2226-8383-2019-20-2-259-272

For citation:


Molchanov V.A., Khvorostukhina E.V. On problem of abstract definability of universal hypergraphic automata by input symbol semigroup. Chebyshevskii Sbornik. 2019;20(2):259-272. (In Russ.) https://doi.org/10.22405/2226-8383-2019-20-2-259-272

Просмотров: 59


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)