Laboratory of Mathematical Logic at PDMI

Пятница, 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'' и показал, что они могут быть использованы для описания параллельных вычислений.