Nonterminal Complexity of Some Operations on Context-Free Languages
Titel:
Nonterminal Complexity of Some Operations on Context-Free Languages
Auteur:
Dassow, Jürgen Stiebe, Ralf
Verschenen in:
Fundamenta informaticae
Paginering:
Jaargang 83 (2008) nr. 1-2 pagina's 35-49
Jaar:
2008-05-27
Inhoud:
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 c_1, c_2, …, c_n and an n-ary operation τ on language, we discuss the range of Var (τ(L_1,L_2,…L_n)) where for 1 ⩽i⩽n, L_i is a context-free language with Var (L_i) = c_i. The operations under discussion are the six AFL-operations: union, concatenation, Kleene-closure, homomorphisms, inverse homomorphisms and intersections by regular sets.
Tijdschrift beschrijving