More on the Size of Higman-Haines Sets: Effective Constructions

• Autorzy: Gruber H. , Holzer M. , Kutrib M.
• Języki publikacji: EN

Abstrakty

EN

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.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 105--121
• Opis fizyczny: bibliogr. 17 poz., tab., wykr.

Twórcy

autor

Gruber H.

autor

Holzer M.

autor

Kutrib M.

• Institut f¨ur Informatik, Ludwig-Maximilians-Universit¨at München Oettingenstr. 67, 80538 München, Germany,

Bibliografia

• [1] Buntrock, G., Otto, F.: Growing Context-Sensitive Languages and Church-Rosser Languages, Inform. Comput., 141, 1998, 1-36.
• [2] Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory, vol. 18 of EATCS Monographs in Theoretical Computer Science, Springer, 1989.
• [3] Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages, Theoret. Comput. Sci., 27, 1983, 311-332.
• [4] Fenner, S., Gasarch, W., Postow, B.: The complexity of finding SUBSEQ(A), Theory Comput. Sys., to appear.
• [5] Fernau, H., Stephan, F.: Characterizations of Recursively Enumerable Sets by Programmed Grammars With Unconditional Transfer, J. Autom., Lang. Comb., 4, 1999, 117-152.
• [6] Gilman, R. H.: A shrinking lemma for indexed languages, Theoret. Comput. Sci., 163, 1996, 277-281.
• [7] Glaister, I., Shallit, J.: A lower bound technique for the size of nondeterministic finite automata, Inform. Process. Lett., 59, 1996, 75-77.
• [8] Gruber, H., Holzer, M., Kutrib, M.: The Size of Higman-Haines Sets, Theoret. Comput. Sci., 387, 2007, 167-176.
• [9] Haines, L. H.: On Free Monoids Partially Ordered by Embedding, J. Combinatorial Theory, 6, 1969, 94-98.
• [10] Harrison, M. A., Yehudai, A.: Eliminating Null Rules in Linear Time, Comput. J., 24, 1981, 156-161.
• [11] Higman, G.: Ordering by Divisibility in Abstract Algebras, Proc. London Math. Soc., 2, 1952, 326-336.
• [12] Holzer, M., Kutrib, M.: Nondeterministic Descriptional Complexity of Regular Languages, Int. J. Found. Comput. Sci., 14, 2003, 1087-1102.
• [13] Ilie, L.: Decision Problems on Orders of Words, Ph.D. thesis, Department of Mathematics, University of Turku, Finland, 1998.
• [14] Kruskal, J. B.: The Theory of Well-Quasi-Ordering: A Frequently Discovered Concept, J. Combinatorial Theory, 13, 1972, 297-305.
• [15] Okhotin, A.: On the state complexity of scattered substrings and superstrings, Turku Centre for Computer Science (TUCS) Technical Report No. 849, Turku, Finland, October 2007.
• [16] van Leeuwen, J.: A Regularity Condition for Parallel Rewriting Systems, SIACT News, 8, 1976, 24-27.
• [17] van Leeuwen, J.: Effective Constructions in Well-Partially-Ordered Free Monoids, Discrete Mathematics, 21, 1978, 237-252.