The Post Correspondence Problem for free groups is undecidable
We prove that the Post Correspondence Problem for finitely generated free groups is undecidable, even when one of the two homomorphisms is injective and has finite-index image. This resolves a longstanding open problem in algorithmic group theory. The proof proceeds through a connection with finite-state transducers. Given a cyclic tag system $\mathcal C$, we effectively construct a finite partial deterministic inverse transducer $\mathcal T_{\mathcal C}$ whose fixed-point set is nontrivial if and only if $\mathcal C$ halts. We then associate to any such transducer two homomorphisms…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.13951
curl -X POST /api/v1/records/arxiv/2607.13951/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.13951/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'