Affiliations: Institut für Informatik,
Ludwig-Maximilians-Universität München, Oettingenstr.
67, 80538 München, Germany. gruberh@tcs.ifi.lmu.de | Institut für Informatik, Technische
Universität München, Boltzmannstr. 3, 85748 Garching
bei München, Germany. holzer@in.tum.de | Institut für Informatik,
Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany.
kutrib@informatik.uni-giessen.de
Note: [] Address for correspondence: Institut für
Informatik, Ludwig-Maximilians-Universität München,
Oettingenstr. 67, 80538 München, Germany
Abstract: A not so well-known result in formal language theory is that the
Higman-Haines sets for any language are regular [11, Theorem 4.4]. It is easily
seen that these sets cannot be effectively computed in general. The
Higman-Haines sets are the languages of all scattered subwords of a given
language as well as the sets of all words that contain some word of a given
language as a scattered subword. Recently, the exact level of unsolvability of
Higman-Haines sets was studied in [8]. Here we focus on language families whose
Higman-Haines sets are effectively constructible. In particular, we study the
size of descriptions of Higman-Haines sets for the lower classes of the Chomsky
hierarchy, namely for the family of regular, linear context-free, and
context-free languages. We prove upper and lower bounds on the size of
descriptions of these sets for general and unary languages.
