Date: Sep 8, 2013 12:03 PM
Author: fom
Subject: Re: abelian square
On 9/8/2013 7:16 AM, Dieter von Holten wrote:

> hi folks,

>

> i found 'abelian squares' in the context of patterns of n symbols of length 2n like 'abcd.cdba' where 'cdba' is a permutation of the first half 'abcd'.

> however, in those texts it is not explained (maybe just not clear enough for me) what is 'abelian' and where is the 'square' ??

>

> any hints ?

>

> thanks

> dvh

>

Looking at the definition in

http://arxiv.org/pdf/0807.5028v1.pdf

both

abcd.cdab

cdab.abcd

satisfy the constraint that the second

string is a permutation of the first.

Since this is true of all finite strings,

one would expect that "abelian" refers

simply to the fact that the two strings

commute over the separator, '.', relative

to the definition.

As for being a "square", that would seem

to be a trickier guess. If you look at

section 2 of the paper,

http://poncelet.math.nthu.edu.tw/disk5/js/computer-science/on_abelian_squares_and_substitut.pdf

you will find that the Parikh vector mentioned

in the first paper is the basis for an

equivalence class as defined in the

second paper.

Relative to this equivalence class, one

has

[x] = [x']

[x][x'] = [x]^2 = [x']^2

So, this would be my guess concerning the

sense of "square" in the name.