Name
Abstract | ||
|---|---|---|
We investigate context-free languages with respect to the measure Prod of descriptional complexity, which gives the minimal number of productions necessary to generate the language. In particular, we consider the behaviour of this measure with respect to operations. For given natural numbers c1,c2,…,cn and an n-ary operation τ on languages, we discuss the set gτ(c1,c2,…,cn) which is the range of Prod(τ(L1,L2,…, Ln)) where, for 1≤i≤n, Li is a context-free language with Prod(Li)=ci. The operations under discussion are union, concatenation, reversal, and Kleene closure. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-31623-4_11 | DCFS |
Keywords | Field | DocType |
measure prod,set g,kleene closure,natural number,descriptional complexity,production complexity,context-free language,n-ary operation,minimal number | Discrete mathematics,Natural number,Context-free language,Kleene star,Pure mathematics,Concatenation,Mathematics | Conference |
Volume | ISSN | Citations |
7386 | 0302-9743 | 1 |
PageRank | References | Authors |
0.37 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Dassow | 1 | 530 | 118.27 |
| Ronny Harbich | 2 | 1 | 1.05 |