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.
