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

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

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

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

Abstract

Отображение

алфавита

в множество всех слов в алфавите

может быть естественным образом продолжено до отображения

множества всех слов в алфавите

(каждая буква

в слове заменяется на ее образ

). Имеется несложный алгоритм распознавать по данному множеству слов

, является ли

инъективным отображением или нет, то есть может ли

быть использовано для кодирования слов алфавите

словами в алфавите

с однозначным декодированием.

Ситуация становится совсем другой, если мы заменим алфавит

на частично коммутативный алфавит, то есть разрешим некоторым буквам меняться местами. В этом случае распознавание инъективности

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

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