Рациональная серия - Rational series

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

Определение

Позволять р быть полукольцо и А конечный алфавит.

А некоммутативный многочлен над А конечная формальная сумма слов над А. Они образуют полукольцо ${\displaystyle R\langle A\rangle }$.

А формальная серия это р-значная функция c, на свободный моноид А^*, который можно записать как

${\displaystyle \sum _{w\in A^{*}}c(w)w\ .}$

Множество формальных рядов обозначается ${\displaystyle R\langle \langle A\rangle \rangle }$ и становится полукольцом при операциях

${\displaystyle c+d:w\mapsto c(w)+d(w)}$

${\displaystyle c\cdot d:w\mapsto \sum _{uv=w}c(u)\cdot d(v)\ .}$

Таким образом, некоммутативный многочлен соответствует функции c на А^* конечной опоры.

В случае, когда р кольцо, то это Кольцо Магнуса над р.^[1]

Если L язык закончился А, рассматриваемый как подмножество А^* мы можем сформировать характеристический ряд из L как формальный ряд

${\displaystyle \sum _{w\in L}w}$

соответствующий характеристическая функция из L.

В ${\displaystyle R\langle \langle A\rangle \rangle }$ можно определить операцию итерация выражается как

${\displaystyle S^{*}=\sum _{n\geq 0}S^{n}}$

и оформлен как

${\displaystyle c^{*}(w)=\sum _{u_{1}u_{2}\cdots u_{n}=w}c(u_{1})c(u_{2})\cdots c(u_{n})\ .}$

В рациональные операции являются сложением и умножением формальных рядов вместе с итерацией. рациональный ряд - формальный ряд, полученный рациональными операциями из ${\displaystyle R\langle A\rangle }$.

Смотрите также

• Формальный степенной ряд
• Рациональный язык
• Рациональный набор
• Серия Hahn (Серия Мальцева – Неймана)
• Весовой автомат

Рекомендации

1. Кох, Гельмут (1997). Алгебраическая теория чисел. Энцикл. Математика. Sci. 62 (2-е издание 1-го изд.). Springer-Verlag. п. 167. ISBN  3-540-63003-1. Zbl  0819.11044.

• Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями. Энциклопедия математики и ее приложений. 137. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-19022-0. Zbl  1250.68007.

дальнейшее чтение

• Сакарович, Жак (2009). Элементы теории автоматов. Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета. Часть IV (где они называются ${\displaystyle \mathbb {K} }$-рациональный ряд). ISBN  978-0-521-84425-3. Zbl  1188.68177.
• Дросте, М., и Куич, В. (2009). Полукольца и формальные степенные ряды. Справочник по взвешенным автоматам, 3–28. Дои:10.1007/978-3-642-01492-5_1
• Сакарович, Дж. Рациональные и узнаваемые степенные ряды. Справочник по взвешенным автоматам, 105–174 (2009). Дои:10.1007/978-3-642-01492-5_4
• В. Куич. Полукольца и формальные степенные ряды: их отношение к формальным языкам и теории автоматов. В Дж. Розенберге и А. Саломаа, редакторах, Справочник по формальным языкам, том 1, глава 9, страницы 609–677. Спрингер, Берлин, 1997 г.