License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-14109
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1410/

Lohrey, Markus

Application of verification techniques to inverse monoids

pdf-format:
Dokument 1.pdf (149 KB)


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, 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.

BibTeX - Entry

@InProceedings{lohrey:DSP:2008:1410,
  author =	{Markus Lohrey},
  title =	{Application of verification techniques to inverse monoids},
  booktitle =	{Algorithmic-Logical 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 =	{1862-4405},
  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, Cayley-graphs, complexity}
}

Keywords: Inverse monoids, word problems, Cayley-graphs, complexity
Seminar: 07441 - Algorithmic-Logical Theory of Infinite Structures
Issue date: 2008
Date of publication: 09.04.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI