Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427006 | Information Processing Letters | 2016 | 6 Pages |
Abstract
•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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christopher S. Henry,