The (nested) word problem

• Extend the deep connection between formal languages and group theory.
• Introduce languages of nested words to the study of the word problem for groups.
• Characterize groups using nested words.
• Demonstrate the potential for using nested words to study groups.

In this paper we provide a new perspective on the word problem of a group by using languages of nested words. These were introduced by Alur and Madhusudan as a way to model data with both a linear ordering and a hierarchically nested matching of items, like HTML or XML documents. We demonstrate how a class of nested word languages called visibly pushdown can be used to study the word problem of virtually free groups in a natural way.