Home

Пятница , 27 мая, 18-00, к.106 (ПОМИ РАН)

Пятница, 27 мая, ауд. 106. Начало в 18:00.

Докладчик: Ю.В. Матиясевич (ПОМИ РАН).

Тема: Разрешимые и неразрешимые случаи проблемы кодирования для частично коммутативных моноидов.

Abstract

Отображение $ \phi:A\rightarrow B^* $ алфавита $ A=\{a_1,\dots,a_n\} $ в множество всех слов в алфавите $ B $ может быть естественным образом продолжено до отображения $ \Phi:A^*\rightarrow B^* $ множества всех слов в алфавите $ A^* $ (каждая буква $ a_i $ в слове заменяется на ее образ $ \phi(a_i) $). Имеется несложный алгоритм распознавать по данному множеству слов $ \{\phi(a_1),\dots,\phi(a_n)\} $, является ли $ \Phi $ инъективным отображением или нет, то есть может ли $ \Phi $ быть использовано для кодирования слов алфавите $ A^* $ словами в алфавите $ B^* $ с однозначным декодированием.

Ситуация становится совсем другой, если мы заменим алфавит $ B $ на частично коммутативный алфавит, то есть разрешим некоторым буквам меняться местами. В этом случае распознавание инъективности $ \Phi $ может оказаться неразрешимой проблемой, но мы до сих пор не имеем полного описания, в каких случаях это происходит. Эта задача имеет тесные связи с автоматами разных типов.

P.~Cartier и D.~Floata начали изучать слова в частично коммутативных алфавитах с комбинаторной точки зрения в 60-х годах прошлого века. Позднее A.~Mazurkievicz дал таким словам название ``traces'' и показал, что они могут быть использованы для описания параллельных вычислений.