id: 05276906
dt: j
an: 05276906
au: Diekert, Volker; Ondrusch, Nicole; Lohrey, Markus
ti: Algorithmic problems on inverse monoids over virtually free groups.
so: Int. J. Algebra Comput. 18, No. 1, 181-208 (2008).
py: 2008
pu: World Scientific, Singapore
la: EN
cc: 
ut: inverse monoids; word problem; Birget-Rhodes expansions; finite
    presentations; rational subsets; decidability; first-order theories;
    membership problem; Cayley graphs
ci: 
li: doi:10.1142/S0218196708004366
ab: Summary: Let $G$ be a finitely generated virtually-free group. We consider
    the Birget-Rhodes expansion of $G$, which yields an inverse monoid and
    which is denoted by $\text{IM}(G)$ in the following. We show that for a
    finite idempotent presentation $P$, the word problem of a quotient
    monoid $\text{IM}(G)/P$ can be solved in linear time on a RAM. The
    uniform word problem, where $G$ and the presentation $P$ are also part
    of the input, is EXPTIME-complete. With $\text{IM}(G)/P$ we associate a
    relational structure, which contains for every rational subset $L$ of
    $\text{IM}(G)/P$ a binary relation, consisting of all pairs $(x,y)$
    such that $y$ can be obtained from $x$ by right multiplication with an
    element from $L$. We prove that the first-order theory of this
    structure is decidable. This result implies that the emptiness problem
    for Boolean combinations of rational subsets of $\text{IM}(G)/P$ is
    decidable, which, in turn implies the decidability of the submonoid
    membership problem of $\text{IM}(G)/P$. These results were known
    previously for free groups, only. Moreover, we provide a new
    algorithmic approach for these problems, which seems to be of
    independent interest even for free groups. We also show that one cannot
    expect decidability results in much larger frameworks than
    virtually-free groups because the subgroup membership problem of a
    subgroup $H$ in an arbitrary group $G$ can be reduced to a word problem
    of some $\text{IM}(G)/P$, where $P$ depends only on $H$. A consequence
    is that there is a hyperbolic group $G$ and a finite idempotent
    presentation $P$ such that the word problem is undecidable for some
    finitely generated submonoid of $\text{IM}(G)/P$. In particular, the
    word problem of $\text{IM}(G)/P$ is undecidable.
rv: