Search

Abstract: In this paper we show that the membership problems for finitely generated submonoids and for rational subsets are recursively equivalent for groups with two or more ends. [Copyright &y& Elsevier]

Abstract: We show that the membership problem in a finitely generated submonoid of a graph group (also called a right-angled Artin group or a free partially commutative group) is decidable if and only if the independence graph (commutation graph) is a transitive forest. As a consequence we obtain the first example of a finitely presented group with a decidable generalized word problem that does not have a decidable membership problem for finitely generated submonoids. We also show that the rational subset membership problem is decidable for a graph group if and only if the independence graph is a transitive forest, answering a question of Kambites, Silva, and the second author [M. Kambites, P.V. Silva, B. Steinberg, On the rational subset problem for groups, J. Algebra 309 (2) (2007) 622–639]. Finally we prove that for certain amalgamated free products and HNN-extensions the rational subset and submonoid membership problems are recursively equivalent. In particular, this applies to finitely generated groups with two or more ends that are either torsion-free or residually finite. [Copyright &y& Elsevier]

Abstract: This paper investigates the word problem for inverse monoids generated by a set Γ subject to relations of the form e = f, where e and f are both idempotents in the free inverse monoid generated by Γ. It is shown that for every fixed monoid of this form the word problem can be solved both in linear time on a RAM as well as in deterministic logarithmic space, 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. [Copyright &y& Elsevier]

Those graph products of groups that are virtually-free are characterized. [ABSTRACT FROM AUTHOR]

Abstract: When a process is capable of executing an unbounded number of non-observable actions it is said to be divergent. Different capabilities of an observer to identify this phenomena along the execution leads to different divergent sensitive semantics. This paper develops sound and complete axiomatisations for the divergence sensitive spectrum of weak bisimulation equivalence. The axiomatisations separates the axioms concerning recursion and those that capture the essence of diverging behaviour. [Copyright &y& Elsevier]

Abstract: The main result of this paper states that the isomorphism problem for ω-automatic trees of finite height is at least has hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies (2008) [12] showing that the isomorphism problem for ω-automatic structures is not in . Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ω-automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to our main results, we show lower and upper bounds for the isomorphism problem for ω-automatic trees of every finite height: (i) It is decidable (-complete, resp.), for height 1 (2, resp.), (ii) -hard and in for height 3, and (iii) - and -hard and in (assuming CH) for height . All proofs are elementary and do not rely on theorems from set theory. [Copyright &y& Elsevier]