Browsing by Author "Ondrusch, Nicole"

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Inverse monoids : decidability and complexity of algebraic questions
    (2005) Lohrey, Markus; Ondrusch, Nicole
    This paper investigates the word problem for inverse monoids generated by a set A subject to relations of the form e=f, where e and f are both idempotents in the free inverse monoid generated by A. It is shown that for every fixed monoid of this form the word problem can be solved in polynomial time which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node x to a node y that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced. Finally, it is shown that the Cayley-graph of the free inverse monoid has an undecidable monadic second-order theory.
  • Thumbnail Image
    ItemOpen Access
    Komplexitäts- und Entscheidbarkeitsresultate für inverse Monoide mit idempotenter Präsentation
    (2006) Ondrusch, Nicole; Diekert, Volker (Prof. Dr.)
    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.