Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: AFL operations

Sortuj według:

Ogranicz wyniki do:

Nonterminal Complexity of Some Operations on Context-Free Languages

Dassow J., Stiebe R.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

35-49

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.