Visibly Pushdown Languages in Groups
For researchers in formal language theory and group theory, this paper clarifies the limitations of VPLs in describing group-theoretic properties.
The paper shows that the word problem of a finitely generated group is a Visibly Pushdown Language (VPL) if and only if the group is finite, and that solving equations in a free group with VPL constraints is undecidable.
In this paper we explore the connections between the class of Visibly Pushdown Languages ($\mathbf{VPL}$) and the natural sets of words one can associate to a finitely generated group. We show that the word problem of a finitely generated group is $\mathbf{VPL}$ exactly when the group is finite. We also show that free reduction does not preserve $\mathbf{VPL}$, and that finding solutions to equations in a free group with $\mathbf{VPL}$ constraints (as reduced words) is undecidable. We explore the structure of sets whose full preimage is $\mathbf{VPL}$, showing these are often recognisable sets. We conjecture that, in any group, this class is precisely the recognisable sets.