Lohrey, Markus
Application of verification techniques to inverse monoids
Abstract
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, EXPTIMEcompleteness is shown.
For the Cayleygraphs of these
monoids, it is shown that the firstorder 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.
BibTeX  Entry
@InProceedings{lohrey:DSP:2008:1410,
author = {Markus Lohrey},
title = {Application of verification techniques to inverse monoids},
booktitle = {AlgorithmicLogical Theory of Infinite Structures},
year = {2008},
editor = {Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
number = {07441},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1410},
annote = {Keywords: Inverse monoids, word problems, Cayleygraphs, complexity}
}
Keywords: 

Inverse monoids, word problems, Cayleygraphs, complexity 
Seminar: 

07441  AlgorithmicLogical Theory of Infinite Structures

Issue date: 

2008 
Date of publication: 

09.04.2008 