On the rational subset problem for groups.

DOI10.1016/J.JALGEBRA.2006.05.020MaRDI QIDQ875109zbMATH OpenOpenAlexFDO

Authors Mark Kambites, Pedro V. Silva, Benjamin Steinberg

Publication date 11 April 2007

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0602454

decidability decision problems finite automata finitely generated groups formal languages graphs of groups rational subset problem regular intersection decision problem word problem

Mathematics Subject Classification ID

Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: We use language theory to study the rational subset problem for groups and monoids. We show that the decidability of this problem is preserved under graph of groups constructions with finite edge groups. In particular, it passes through free products amalgamated over finite subgroups and HNN extensions with finite associated subgroups. We provide a simple proof of a result of Grunschlag showing that the decidability of this problem is a virtual property. We prove further that the problem is decidable for a direct product of a group G with a monoid M if and only if membership is uniformly decidable for G-automata subsets of M. It follows that a direct product of a free group with any abelian group or commutative monoid has decidable rational subset membership.

Review text

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\).

Recommendations

Cites work

Cited in

(46)

This page was built for publication: On the rational subset problem for groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q875109)