Nonterminal Complexity of Some Operations on Context-Free Languages

• Autorzy: Dassow J. , Stiebe R.
• Języki publikacji: EN

Abstrakty

EN

We investigate context-free languages with respect to the measure Var of descriptional complexity, which gives the minimal number of nonterminals necessary to generate a language. More specifically, we consider the behaviour of this measure with respect to language-theoretic operations. For given numbers c1,c2,... ,cn and an n-ary operation t on languages, we discuss the range of Var(t(L1,L2,... , Ln)) where, for 1 ≤ i ≥ n, Li is a context-free language with Var(Li)=ci. The operations under discussion are the six AFL-operations: union, concatenation, Kleene-closure, homomorphisms, inverse homomorphisms and intersections by regular sets.

Słowa kluczowe

EN

context-free language; descriptional complexity; AFL operations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 83, nr 1-2
• Strony: 35--49
• Opis fizyczny: bibliogr. 11 poz., tab.

Twórcy

autor

Dassow J.

autor

Stiebe R.

• Otto-von Guericke Universität Magdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg , Germany,

Bibliografia

• [1] Campeanu, C, Culik II, K., Salomaa, K., Yu, Sh.:, State complexity of basic operations on finite languages. In: Proc. Workshop on Implementing Automata 1994, LNCS 2214, Springer-Verlag, Berlin, 2001, 60-70.
• [2] Domaratzki, M., Salomaa, K.: Transition complexity of language operations. In: Proc. Descriptional Complexity of Formal Systems 2006, New Mexico State Univ. Las Cruces, 2006, 141-152.
• [3] Gruska, J.: On a classification of context-free languages. Kybernetika 3 (1967) 22-29.
• [4] Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. International Journal of Foundations of Computer Science 14 (2003) 1087-1102.
• [5] Jirasek, J., Jiraskova, G., Szabari, A.: State complexity of concatenation and complement of regular languages. In: Proc. Conference on Implementation and Application of Automata 2004, LNCS 3317, Springer-Verlag, Berlin, 2004, 178-189.
• [6] Jiraskova, G., Okhotin, A.: State complexity of cyclic shift. In: Proc. Descriptional Complexity of Formal Systems 2005, Univ. Milano, 2005, 182-193.
• [7] Paun, Gh.: On the smallest number of nonterminals required to generate a context-free language. Mathematica - Revue a"Analyse Numerique et de la Theorie de VApproximation 18 (1976) 203-208.
• [8] Salomaa, K.: Descriptional complexity of nondeterministic finite automata. In: Developments in Language Theory, LNCS 4588, Springer-Verlag, Berlin, 2007, 31-35.
• [9] Yu, Sh.: State complexity of regular languages. Journal of Automata, Languages and Combinatorics 6 (2001) 221-234.
• [10] Yu, Sh.: State complexity of finite and infinite regular languages. Bulletin of the EATCS 76 (2002) 142-152.
• [11] Yu, Sh., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoretical Computer Science 125 (1994) 315-328.