Пятница, 26 октября, ауд. 203. Начало в 18:15.
Докладчик: Александр Охотин (University of Turku).
Тема: Обратимость вычислений графоходных автоматов.
Abstract
В докладе предлагается общее представление детерминированных автоматов, обходящих конечные неориентированные структуры, в виде графоходных автоматов. Этим отвлечённым понятием описываются такие известные модели, как двухсторонние конечные автоматы, в том числе их многоленточные и многоголовочные разновидности, древоходные автоматы и их расширение с камешками, автоматы на картинках, машины Тьюринга с ограниченной памятью, и т.д. Показывается, что всякий графоходный автомат может быть преобразован к равносильному ему обратимому графоходному автомату, в котором каждый шаг вычисления логически обратим. Преобразование осуществляется с линейным ростом числа внутренних состояний, где множитель зависит от степени вершин рассматриваемых графов. Результат применим ко всем вычислительным моделям, представленным графоходными автоматами. Доклад по совместной работе с М. Кунцем из Брненского университета им. Масарика.
