Komplexitäts- und Entscheidbarkeitsresultate für inverse Monoide mit idempotenter Präsentation

Abstract

Wir haben eine Konstruktion inverser Monoide $FIM(\Gamma)/P$ und $IM(G)/P$, beruhend auf Arbeiten von Birget und Rhodes sowie Margolis und Meakin betrachtet und konnten für dies speziellen Klassen inverser Monoide mit idempotenter Präsentation die Entscheidbarkeit des Wortproblems in linearer Zeit (auf einer RAM) zeigen. Ferner ist das uniforme Wortproblem für diese inversen Monoide EXPTIME-vollständig.

Wir haben ferner die relationale Struktur $\C(\IM(G)/P)$ mit Prädikat $\reach_L$ betrachtet. Hierfür konnten wir die FO-Theorie auf die MSO-Theorie des Cayeyleygraphen von $G$ reduzieren und haben damit die Entscheidbarkeit der FO-Theorie von $\C(\IM(G)/P)$ erhalten. Diese impliziert, wie wir in Kapitel \ref{rationale mengen} gesehen haben, eine Reihe weiterer Resultate, insbesondere die Entscheidbarkeit des verallgemeinerten Wortproblems für $\IM(G)/P$ sowie die Entscheidbarkeit des Leerheitsproblems für boolesche Kombinationen rationaler Mengen in $\IM(G)/P$. Es stellt sich die Frage, für welche Monoide $M$ die Struktur $\C(M)$ noch entscheidbar ist, bzw. für welche Monoide Unentscheidbarkeit gezeigt werden kann.

We focus here on a special class of monoids -- inverse monoids, which lie somewhere between monoids and groups. As groups arise naturally as bijections over a set, inverse monoids arise as monoids of partially defined injections over a set. We consider a special kind of inverse monoids following Birget and Rhodes (and Margolis and Meakin) and denote this inverse monoid by $IM(G)/P$ ($FIM(\Gamma)/P$).

We show that the word problem for these inverse monoids is decidable. Moreover the uniform word problem ist EXPTIME-complete.

Furthermore we consider a relational structure $C(IM(G)/P)$ with a predicate $reach_L$ for any rational set $L$ in $IM(G)/P$ and show that the first-order theory for this monoid is decidable. Same further decidablility results follow.