Konferenzpaper

Jahr der Veröffentlichung: 2007

Seiten: 167-176

Zeitschrift: Theoretical Computer Science

Bandnummer: 387

Heftnummer: 2

ISSN: 0304-3975

DOI Link: https://doi.org/10.1016/j.tcs.2007.07.036

Konferenz: 8th International Workshop on Descriptional Complexity of Forman Systems

Verlag: Elsevier

Abstract: 
We show that for the family of Church-Rosser languages the Higman-Haines sets, which are the sets of all scattered subwords of a given language and the sets of all words that contain some word of a given language as a scattered subword, cannot be effectively constructed, although both these sets are regular for any language. This nicely contrasts the result on the effectiveness of the Higman-Haines sets 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 sets, 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 family of regular languages we prove an upper and a matching lower bound on the size of the Higman-Haines sets in terms of nondeterministic finite automata. (C) 2007 Published by Elsevier B.V.

Harvard-Zitierstil: Gruber, H., Holzer, M. and Kutrib, M. (2007) The size of Higman-Haines sets, Theoretical Computer Science, 387(2), pp. 167-176. https://doi.org/10.1016/j.tcs.2007.07.036

APA-Zitierstil: Gruber, H., Holzer, M., & Kutrib, M. (2007). The size of Higman-Haines sets. Theoretical Computer Science. 387(2), 167-176. https://doi.org/10.1016/j.tcs.2007.07.036