a problem with words

[Michel BILLAUD]

NOTATIONS. Let A={a,b,c...} be a finite alphabet, A* the set of words over
A, equipped with the concatenation "." (omitted unless necessary) and the
empty word denoted by 1.

Every f: A -> A* defines a morphism (also named f) from A* to A*,
the image of a word w being the concatenation of the images by f
of its letters.
For example, if f(a)=ab and f(b)=aa,
then f(abba)=f(a).f(b).f(b).f(a)=abaaaaab

For any letter x in A, delta_x is the morphism which deletes all
occurrences of the letter x, and keeps all others, that is:
delta_x (y) = 1 if x=y, otherwise y

DEFINITION. A word w is "simple" if for every morphism f
f(w)=w implies f(x)=x for each letter x in w

EXAMPLES of "simple" words : a,aa,aaa, abba, aabb, abcbac ...
non-simple words: ab, abab (take f(a)=ab and f(b)=1)
abcbca ( f(a)=a, f(b)=bc, f(c)=1 )

QUESTION. For every non-empty "simple" word w, does there always
exist a letter x in w such that delta_x(w) is also simple ?

EXAMPLE: for w=abcbac, take x=c, then delta_c(abcbac)=abba is simple.

Couldn't find a proof, or a counter-example... Help appreciated !

--
Michel BILLAUD : bil...@geocub.greco-prog.fr
Departement d'Informatique : phone W: 56.84.57.92 // 56.84.69.22
IUT "A", Universite Bordeaux I : "Personne n'est exempt de dire des sottises.
33405 Talence (FRANCE) : Le malheur est de les dire curieusement"

[Cris Moore]

I think this is a sweet problem.

What is the language of simple words? Is it even decidable?
Do you have any simple algorithms for telling that a word is simple?

- Cris Moore, Santa Fe Institute mo...@santafe.edu

[Michael Hirsch]

>>>>> On Thu, 11 Feb 93 00:50:50 GMT, mo...@aztec.santafe.edu (Cris Moore) said:

Cris> I think this is a sweet problem.

I agree.

Cris> What is the language of simple words? Is it even decidable?
Cris> Do you have any simple algorithms for telling that a word is simple?

It is definitely decidable. Suppose the alphabet has size |A| = a,
and the input x has length = s. If f(x) = x then each letter of x is
assigned some substring of x, so there are O(n^2) possible assignments
for each letter for a total of only O(n^2)^s = O(n^2s) possible maps.
So for a given alphabet size the recognition problem is poly-time
decidable. If s = O(n) then this algorithm is exponential but clearly
in NP.

--

Michael D. Hirsch mhi...@cs.princeton.edu
Computer Science Department Voice: (609) 258-1751
Princeton NJ, 08544 FAX: (609) 258-1771

[Michel BILLAUD]

In article <-qv...@SantaFe.edu>, mo...@aztec.santafe.edu (Cris Moore) writes:
|> I think this is a sweet problem.
|>
|> What is the language of simple words?

Thars precisely what we're looking for !

|> Is it even decidable?
|> Do you have any simple algorithms for telling that a word is simple?

Of course. The "brute-force" one. Given a word w, try all morphisms f
such that for every letter x in w |f(x)| <= |w|. Check that f(w)=w.
Print "no" if f is non-trivial, print "yes" if there's none.

Michel.

PS: Of course there is an obvious smaller bound |f(x)|* |w|_x <= |w|,
and also we can generate candidates for f from w, etc.