Замкнутое полукольцо: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Замкнутое полукольцо''' (''Closed semiring'') - полукольцо <math>S</math> с двумя дополнит...)
 
Нет описания правки
Строка 1: Строка 1:
'''Замкнутое полукольцо''' (''Closed semiring'') -  
'''Замкнутое полукольцо''' (''[[Closed semiring]]'') - полукольцо <math>S</math> с двумя дополнительными свойствами: (а) если <math>a_{1}, a_{2}, \ldots, a_{n}, \ldots</math> есть счетная
полукольцо <math>S</math> с двумя дополнительными свойствами: (а) если
последовательность элементов <math>S</math>, то существует и является единственной сумма  
<math>a_{1}, a_{2}, \ldots, a_{n}, \ldots</math> есть счетная
последовательность элементов <math>S</math>, то существует и является
единственной сумма  


<math>a_{1} + a_{2} + \ldots + a_{n} +
<math>a_{1} + a_{2} + \ldots + a_{n} + \ldots,</math>  
\ldots,</math>  


причем порядок, в котором производится сложение
причем порядок, в котором производится сложение различных элементов, несуществен; (б) операция умножения "<math>\cdot</math>" дистрибутивна относительно конечных и счетно-бесконечных сумм. На замкнутых полукольцах может быть определена унарная операция, называемая замыканием. Пусть
различных элементов, несуществен; (б) операция умножения
"<math>\cdot</math>" дистрибутивна относительно конечных и
счетно-бесконечных сумм. На замкнутых полукольцах может быть
определена унарная операция, называемая замыканием. Пусть
<math>a</math> --- некоторый элемент из <math>S</math>; тогда степени <math>a</math> могут
<math>a</math> --- некоторый элемент из <math>S</math>; тогда степени <math>a</math> могут
быть определены следующим образом:  
быть определены следующим образом:  
Строка 32: Строка 24:
<math>a^{\ast} = 1 + a \cdot a^{\ast}.</math>
<math>a^{\ast} = 1 + a \cdot a^{\ast}.</math>


Замкнутые полукольца находят применения в различных областях
Замкнутые полукольца находят применения в различных областях вычислительной техники: в теории автоматов, теории грамматик, теории рекурсии и неподвижных точек, последовательных машинах, матричной обработке, а также в решении различных задач теории графов, например при разработке алгоритмов нахождения [[кратчайший путь|кратчайших путей]], транзитивного замыкания и др.
вычислительной техники: в теории автоматов, теории грамматик, теории
рекурсии и неподвижных точек, последовательных машинах, матричной
обработке, а также в решении различных задач теории графов, например
при разработке алгоритмов нахождения кратчайших путей, транзитивного
замыкания и др.
==Литература==
==Литература==
[Словарь],  
[Словарь],  


[Ахо-Хопкрофт-Ульман]
[Ахо-Хопкрофт-Ульман]

Версия от 17:40, 20 октября 2009

Замкнутое полукольцо (Closed semiring) - полукольцо [math]\displaystyle{ S }[/math] с двумя дополнительными свойствами: (а) если [math]\displaystyle{ a_{1}, a_{2}, \ldots, a_{n}, \ldots }[/math] есть счетная последовательность элементов [math]\displaystyle{ S }[/math], то существует и является единственной сумма

[math]\displaystyle{ a_{1} + a_{2} + \ldots + a_{n} + \ldots, }[/math]

причем порядок, в котором производится сложение различных элементов, несуществен; (б) операция умножения "[math]\displaystyle{ \cdot }[/math]" дистрибутивна относительно конечных и счетно-бесконечных сумм. На замкнутых полукольцах может быть определена унарная операция, называемая замыканием. Пусть [math]\displaystyle{ a }[/math] --- некоторый элемент из [math]\displaystyle{ S }[/math]; тогда степени [math]\displaystyle{ a }[/math] могут быть определены следующим образом:

[math]\displaystyle{ a^{0} = 1; }[/math]

[math]\displaystyle{ a^{n} = a \cdot a^{n-1}\mbox{ для всех } n \gt 0. }[/math]

Тогда замыкание [math]\displaystyle{ a^{\ast} }[/math] можно определить как

[math]\displaystyle{ a^{\ast} = 1 + a + a^{2} + \ldots + a^{n} + \ldots. }[/math]

Из свойств полуколец вытекает, что

[math]\displaystyle{ a^{\ast} = 1 + a \cdot a^{\ast}. }[/math]

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

Литература

[Словарь],

[Ахо-Хопкрофт-Ульман]