pith. sign in

arxiv: 1104.1806 · v1 · pith:ASTC2GR4new · submitted 2011-04-10 · 🧮 math.GR · cs.FL

Groups with poly-context-free word problem

classification 🧮 math.GR cs.FL
keywords groupspoly-context-freeconjectureproblemsolublewordfinitelylanguages
0
0 comments X
read the original abstract

We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.