Laboratory of Mathematical Logic at PDMI

Пятница, 14 октября, ауд. 311. Начало в 15:00.

Докладчик: Juhani Karhumaki (University of Turku).

Тема: REACHABILITY VIA COOPERATING MORPHISMS.

Abstract

The goal of this presentation is to analyze the equality mechanism of cooperating morphisms of free monoids, and to point out that the reachability questions lead to the undecidability and easy characterizations of recursively enumerable languages. In particular, we aim to show, what subconstructions are needed in such results. Moreover, we recall that in some cases the undecidability of the reachability is achieved although the sets of all reachable objects are simple, or more formally, regular languages.