REVIEW
On the rational subset problem for groups
Group Theory · Submitted 21 Feb 2006 · 42 references
Pith's verdict: A genuinely useful paper with a patchable gap in the main proof: Theorem 5.1's claimed equality L = W∩P is false, but the theorem survives with a small amendment.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Decidability of rational subset membership is preserved under graphs of groups with finite edge groups, and for direct products with free groups it is equivalent to uniform decidable membership for context-free subsets.
The reading
The authors use this equivalence to prove two main families of results. First, if a group is assembled from simpler groups by a graph of groups construction in which the edge groups are finite, for example free products amalgamated over finite subgroups or HNN extensions with finite associated subgroups, then the assembled group has a decidable rational subset problem exactly when all the pieces do. The proof works by encoding the word problem as the ancestor language of a monadic rewriting system and showing that the relevant language property is preserved.
Second, for a direct product of a free group with a monoid, they show that decidability of the rational subset problem is equivalent to the uniform decidability of membership for context-free subsets of the monoid. This yields new decidability results for direct products of free groups with abelian groups and commutative monoids. The paper also reproves several known results, such as Grunschlag's theorem that decidability is a virtual property, with simpler language-theoretic proofs.
Extended reading notes
Core claim
Theorem 5.1: Let (G, Y) be a finite, connected, non-empty graph of finitely generated groups with finite edge groups. Then the fundamental group of (G, Y) has decidable rational subset problem if and only if every vertex group has decidable rational subset problem. This is the main load-bearing assertion: decidability of rational subset membership is preserved under graphs of groups with finite edge groups, and the equivalence is effective.
Load-bearing premise
The proof of Theorem 5.1 depends on the normal form theorem for fundamental groups of graphs of groups, cited as [38, Theorem I.11] in Section 5. This theorem guarantees that every non-empty word of cycle type that represents the identity must contain a subword y w \bar{y} where w represents an element of the edge group. If this structural fact failed, the induction showing W ∩ P = L would collapse. It is a standard but deep result of Bass-Serre theory, quoted rather than proved in the present paper.
Original 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We use language theory to study the rational subset problem for groups and monoids. | contribution 0.59 | 0.88 | 0.05 | asserted 0.96 |
| s1 | We show that the decidability of this problem is preserved under graph of groups constructions with finite edge groups. | result 0.98 | 0.94 | 0.38 | asserted 1.00 |
| s2 | In particular, it passes through free products amalgamated over finite subgroups and HNN extensions with finite associated subgroups. | result 0.70 | 0.71 | 0.12 | asserted 1.00 |
| s3 | We provide a simple proof of a result of Grunschlag showing that the decidability of this problem is a virtual property. | result 0.51 | 0.83 | 0.09 | asserted 1.00 |
| s4 | 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. | result 0.99 | 0.94 | 0.20 | asserted 1.00 |
| s5 | It follows that a direct product of a free group with any abelian group or commutative monoid has decidable rational subset membership. | result 0.65 | 0.87 | 0.16 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.