Seminár z teoretickej informatiky - Tatiana Jajcayová (8.4.2016)

v piatok 8.4.2016 o 11:00 hod. v miestnosti M/213

04. 04. 2016 15.28 hod.
Od: Rastislav Kráľovič

Prednášajúci: Tatiana Jajcayová

Názov: The word problem in Free Inverse Monoids

Termín: 8.4.2016, 11:00 hod., M/213

Abstrakt:
In our presentation, we will address some algorithmic questions (the Word Problem, for instance) about presentations of inverse monoids by considering automata rising from these presentations. The automata are in general infinite, but in specific cases we are able to detect so called finite core - in the sense that all important information about the automaton is encoded in a "finite" subgraph. We introduced certain classes of HNN-extensions for which we were able to provide an iterative procedure for building these automata, and show that in some cases this procedure yields an effective construction, and thus provides a solution for the word problem. We analyze conditions under which the procedure is effective and show that the word problem is decidable in particular for HNN-extensions of free inverse monoids.