The (Nested) Word Problem

2013/10/23 by Christopher S. Henry, Henry, Christopher S.
Computer Science · Mathematics · #03D40 #20E05 #20F10 #68Q45 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR) #cs.FL #math.GR #msc:03D40 #msc:20E05 #msc:20F10 #msc:68Q45

paper · pdf · doi:10.48550/arxiv.1310.6283

1 figure

arxiv created 2014/10/27 · arxiv updated 2014/10/28

Abstract

In this article 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 programming languages such as HTML. 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.

Related

• On groups whose word problem is solved by a nested stack automaton
• A note on Context Sensitive languages and Word Problems
• Groups that do and do not have context-sensitive word problem
• An application of the Deutsch-Josza algorithm to formal languages and the word problem in groups
• A robust class of languages of 2-nested words