Preview

Машиностроение и компьютерные технологии

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

О некоторых свойствах полуколец

https://doi.org/10.24108/0318.0001379

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

Аннотация

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

Наряду с этим,  и в плане подготовки к доказательству основной теоремы, рассматриваются следующие важные свойства замкнутых полуколец и полуколец с итерацией.

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

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

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

Всё вышеизложенное служит основой доказательства основной теоремы, в которой понятие автомата над полукольцом играет главную роль.

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

Об авторе

А. И. Белоусов
МГТУ им. Н.Э. Баумана, Москва
Россия


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

1. Варанкина В.И., Вечтомов Е.М. Функциональная алгебра и полукольца: результаты исследований 2016 года // Математический вестник педвузов и университетов Волго-Вятского региона. 2017. № 19. С. 36-53.

2. Чермных В.В. Полукольцо натуральных чисел как базовая модель изучения полуколец // Вестник Вятского гос. гуманитарного ун-та. 2012. Т. 3. № 1. С. 62-65.

3. Izhakian Z., Knebusch M., Rowen L. Categories of layered semirings // Communications in Algebra. 2015. Vol. 43. No. 5. Pp. 1807-1836. DOI: 10.1080/00927872.2013.878838

4. Beasley L.B., Seok-Zun Song. Linear operators that preserve term ranks of matrices over semirings // Bull. of the Malaysian Math. Sciences Soc. 2014. Vol. 37. No. 3. Pp. 719-725. Режим доступа: http://math.usm.my/bulletin/pdf/v37n3p10.pdf (дата обращения 2.04.2018).

5. Katsov Y., Tran Giang Nam, Zumbragel J. On simpleness of semirings and complete semirings // J. of Algebra and its Applications. 2014. Vol. 13. No. 6. 29 p. DOI: 10.1142/S0219498814500157

6. Шматков В.Д. Изоморфизмы и автоморфизмы матричных алгебр над полукольцами // Фундаментальная и прикладная математика. 2014. Т. 19. № 6. С. 251-260. Режим доступа: www.mathnet.ru/links/eeeec85f67f4c531f513eb891d5cb796/fpm 1623.pdf (дата обращения 02.04.2018).

7. Вечтомов Е.М. Полукольца и их применения // Математический вестник педвузов и университетов Волго-Вятского региона. 2014. № 16. С. 67-72.

8. Вечтомов Е.М., Варанкина В.И. Полукольца и их применения. III // Математический вестник педвузов и университетов Волго-Вятского региона. 2015. № 17. С. 54-66.

9. Алешников С.И., Болтнев Ю.Ф., Език З., Ишанов С.А, Куих В. Формальные языки и автоматы VII: формальные ряды деревьев (часть I) // Вестник Балтийского федерального ун-та им. И. Канта. Сер.: Физико-матем. и техн. науки. 2011. № 10. С. 5-32.

10. Алешников С.И., Болтнев Ю.Ф., Език З., Ишанов С.А, Куих В. Формальные языки и автоматы V: пары полукольцо-полумодуль Конвея и конечные автоматы // Вестник Балтийского федерального ун-та им. И. Канта. Сер.: Физико-матем. и техн. науки. 2009. № 10. С. 6-42.

11. Никулина Н.С. Полукольцо перечисления всех простых путей в орграфе // Математический вестник педвузов и университетов Волго-Вятского региона. 2011. № 13. С. 132-136.

12. Белоусов А.И., Ткачев С.Б. Дискретная математика: учебник. 5-е изд. М.: Изд-во МГТУ им. Н.Э. Баумана, 2015. 744 с.

13. Вечтомов Е.М., Петров А.А. Полукольца с идемпотентным умножением // Вестник Сыктывкарского ун-та. Сер. 1: Математика. Механика. Информатика. 2011. № 14. С. 21-32.

14. Блюмин С.Л., Жбанов С.А. Идемпотентная математика: некоторые предпосылки и приложения // Вести высших учебных заведений Черноземья. 2011. № 2(24). С. 41-45.

15. Чупраков Д.В. Криптографические алгоритмы над абстрактными полукольцами // Электронные информационные системы. 2016. № 3(10). С. 90-96.

16. Николаев Д.А. Динамические системы с двумерным параметром над идемпотентными полукольцами для моделирования движения мультиагентных систем // Системы управления и информационные технологии. 2012. Т. 48. № 2. С. 22-26.

17. Вечтомов Е.М. Курс по выбору «Функциональная алгебра и полукольца» для аспирантов-математиков // Современные проблемы науки и образования. 2015. № 2-2. С. 318.

18. Kuich W. Automata and languages generalized to ꙍ-continuous semirings // Theoretical Computer Science. 1991. Vol. 79. No. 1. Pp. 137-150. DOI: 10.1016/0304-3975(91)90147-T

19. Белоусов А.И. О методике изложения некоторых разделов теории формальных языков: леммы о разрастании // Инженерный вестник МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 12. С. 1020-1031. Режим доступа: http://engbul.bmstu.ru/doc/828263.html (дата обращения: 23.12.15).


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


Белоусов А.И. О некоторых свойствах полуколец. Машиностроение и компьютерные технологии. 2018;(3):35-50. https://doi.org/10.24108/0318.0001379

For citation:


Belousov A.I. On Some Properties of Semi-rings. Mechanical Engineering and Computer Science. 2018;(3):35-50. (In Russ.) https://doi.org/10.24108/0318.0001379

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


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


ISSN 2587-9278 (Online)