|
We show that for the family of Church-Rosser languages the
Higman-Haines set, that is the set of all scattered subwords of a
given language, cannot be effectively constructed, although this set
is regular for {\em any\/} language. This nicely contrasts the
result on the effectiveness of the Higman-Haines set for the family
of context-free languages. The non-effectiveness is based on a
non-recursive trade-off result between the language description
mechanism of Church-Rosser languages and the corresponding
Higman-Haines set, which in turn is also valid for all supersets of
the language family under consideration, and in particular for the
family of recursively enumerable languages. Finally, for the other
end of the Chomsky hierarchy, namely for the family of regular
languages, we prove an upper and a matching lower bound on the size
of the Higman-Haines set in terms of non-deterministic finite
automata. This is a joint work with Martin Kutrib from the Universität Giessen
|
Mi, 31.05.2006