Journalartikel

Jahr der Veröffentlichung: 2009

Seiten: 105-121

Zeitschrift: Fundamenta Informaticae

Bandnummer: 91

Heftnummer: 1

ISSN: 0169-2968

DOI Link: https://doi.org/10.3233/FI-2009-0035

Konferenz: 6th International Machines, Computations and Universality Conference

Verlag: SAGE Publications

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.

Harvard-Zitierstil: Gruber, H., Holzer, M. and Kutrib, M. (2009) More on the Size of Higman-Haines Sets: Effective Constructions, Fundamenta Informaticae, 91(1), pp. 105-121. https://doi.org/10.3233/FI-2009-0035

APA-Zitierstil: Gruber, H., Holzer, M., & Kutrib, M. (2009). More on the Size of Higman-Haines Sets: Effective Constructions. Fundamenta Informaticae. 91(1), 105-121. https://doi.org/10.3233/FI-2009-0035