Conference paper

Publication year: 2007

Pages: 167-176

Journal: Theoretical Computer Science

Volume number: 387

Issue number: 2

ISSN: 0304-3975

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

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

Publisher: 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 Citation style: 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 Citation style: 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