[comp.theory] word relations

fernau@ira.uka.de (Henning Fernau) (04/25/91)

Dear netters!

I should appreciate your help in the following matter:

I (well, we all) know that there is a huge amount of literature
on word relations of the form $L\subset\Sigma^{\ast}$, i.e. on the
`classical' formal languages.
Alas, I know only _very_ few articles dealing with relations of the
form $R\subset(\Sigma^\ast)^n$ with $n\gt 1$. If you know anything in
this area, would you please send pointers to literature etc.? Are
there any accepted hierarchies of families of word relations like the
Chomsky hierarchy in language theory?
The same question arises when you consider $\omega$-languages (or
relations, respectively).

If there is a considerable interest in the net community, I should
like to post a summary of the received answers.

Thanks in advance,

Henning Fernau
Lehrstuhl Informatik fuer Ingenieure und Naturwissenschaftler
University of Karlsruhe
Am Fasanengarten 5
W-7500 Karlsruhe 1

phone: [West Germany](0721)608-4336
email:fernau@ira.uka.de