The non-abelian squares are not context-free

2011/10/18 by Tan, Shuo
Arts and Humanities · Computer Science · #68Q45 #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Historical Linguistics and Language Studies #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1110.4136

openalex publication_date 2011/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Answering a recent question of Crochemore, we prove that the language of words that are not abelian squares is not context-free.

Related

• On the context-freeness of the set of words containing overlaps
• There are exponentially many ternary words that avoid abelian cubes
• Abelian Primitive Words
• Observations and Problems on k-abelian avoidability
• Solved and unsolved problems about abelian squares