2026-07-23T08:19:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1410 2024-03-06T11:07:45Z ddc:004 open_access

Application of verification techniques to inverse monoids Lohrey, Markus Inverse monoids word problems Cayley-graphs complexity The word problem for inverse monoids generated by a set $Gamma$ subject to relations of the form $e=f$, where $e$ and $f$ are both idempotents in the free inverse monoid generated by $Gamma$, is investigated. 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, some results on free partially commutative inverse monoids are presented. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Lohrey 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07441.3 urn:nbn:de:0030-drops-14109 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.3 eng https://creativecommons.org/licenses/by/4.0/legalcode