On strongly context-free languages. (English) Zbl 0958.68084
Summary: We investigate the context-free languages whose complements are also context-free. We call them strongly context-free languages. The family of strongly linear languages is similarly defined. After examining the closure properties of the family of strongly context-free languages, we prove that any slender context-free language is strongly linear. We then show that there are languages of a bounded complexity in terms of the number of non-terminals or productions necessary to generate them, whereas the complexity of their complements is arbitrarily large.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Adleman, L. M., Molecular computation of solutions to combinatorial problems, Science, 226, 1021-1024 (1994) |
| [2] | Berstel, J., Every iterated morphism yields a co-CFL, Inform. Process. Lett., 22, 1, 7-9 (1986) · Zbl 0584.68082 |
| [3] | Bucher, W.; Culik II, K.; Maurer, H. A.; Wotschke, D., Concise description of finite languages, Theoret. Comput. Sci., 14, 227-246 (1981) · Zbl 0469.68081 |
| [4] | Calude, C.; Yu, S., Language-theoretic complexity of disjunctive sequences, Discrete Appl. Math., 80, 203-209 (1997) · Zbl 0894.68091 |
| [5] | J. Gruska, Descriptional complexity of context-free languages. Proceedings of the MFCS Symposium, High Tatras, 1973, pp. 71-83.; J. Gruska, Descriptional complexity of context-free languages. Proceedings of the MFCS Symposium, High Tatras, 1973, pp. 71-83. |
| [6] | M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, MA, 1978.; M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, MA, 1978. · Zbl 0411.68058 |
| [7] | Honkala, J., On slender languages, Bull. EATCS, 64, 145-152 (1998) · Zbl 0898.68042 |
| [8] | Honkala, J., On a problem of G. Păun, Bull. EATCS, 64, 341 (1998) |
| [9] | Ilie, L., On a conjecture about slender context-free languages, Theoret. Comput. Sci., 132, 427-434 (1994) · Zbl 0938.68707 |
| [10] | L. Ilie, On lengths of words in context-free languages, Theoret. Comput. Sci., in press.; L. Ilie, On lengths of words in context-free languages, Theoret. Comput. Sci., in press. · Zbl 0944.68099 |
| [11] | V. Manca, C. Martin-Vide, Gh. Păun, New computing paradigms suggested by DNA computing: Computing by carving, in: L. Kari, H. Rubin, D.H. Wood (Eds.), Proceedings of the fourth International Meeting on DNA Based Computers, Pennsylvania Univ., June 1998, pp. 41-56.; V. Manca, C. Martin-Vide, Gh. Păun, New computing paradigms suggested by DNA computing: Computing by carving, in: L. Kari, H. Rubin, D.H. Wood (Eds.), Proceedings of the fourth International Meeting on DNA Based Computers, Pennsylvania Univ., June 1998, pp. 41-56. |
| [12] | Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A., DNA solution of the maximal clique problem, Science, 278, 446-449 (1997) |
| [13] | Păun, Gh., A positive answer to problem P11, Bull. EATCS, 19, 9-10 (1983) |
| [14] | Gh. Păun, G. Rozenberg, A. Salomaa, DNA Computing. New Computing Paradigms, Springer, Berlin, 1998.; Gh. Păun, G. Rozenberg, A. Salomaa, DNA Computing. New Computing Paradigms, Springer, Berlin, 1998. · Zbl 0940.68053 |
| [15] | Păun, Gh.; Salomaa, A., Thin and slender languages, Discrete Appl. Math., 61, 257-270 (1995) · Zbl 0831.68057 |
| [16] | G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, 3 volumes, Springer, Heidelberg, 1997.; G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, 3 volumes, Springer, Heidelberg, 1997. · Zbl 0866.68057 |
| [17] | Salomaa, A., On the index of a context-free grammar and language, Inform. and Control, 14, 474-477 (1969) · Zbl 0181.31001 |
| [18] | A. Salomaa, Formal Languages, Academic Press, New York, 1973.; A. Salomaa, Formal Languages, Academic Press, New York, 1973. · Zbl 0262.68025 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
