On the rational subset problem for groups. (Q875109): Difference between revisions

Let \(M\) be a monoid generated by a subset \(A\), \(W_A(M,m)\) the set of all words in \(A^*\) representing the element \(m\in M\). The regular intersection decision (RID) problem for a language \(L\subseteq\Sigma^*\) is the problem of deciding whether the language recognized by a finite automaton over \(\Sigma\) has non-empty intersection with \(L\). If a group \(G\) is generated by a finite subset \(A\), then the three properties are equivalent: (i) rational subset membership is decidable; (ii) the word problem with respect to \(A\) is RID; (iii) the RID-problem for \(W_A(G,g)\) is uniformly decidable. This observation is used to establish several connections between algorithmic group theory and formal language theory. It is shown that decidability of the rational subset problem is preserved under graph of groups constructions with finite edge groups, e.g., it is shown that if \((G,Y)\) is a finite, connected graph of finitely generated groups with finite edge groups then the rational subset problem is decidable in the fundamental group of \((G,Y)\) iff it is decidable in every vertex group and the rational subset problem for the direct product \(G\times M\) of a finitely generated group \(G\) and a finitely generated monoid \(M\) is decidable iff membership is uniformly decidable for \(G\)-automaton subsets of \(M\).