Name
Title | ||
|---|---|---|
Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars |
Abstract | ||
|---|---|---|
We refine the classical notion of the nonterminal complexity of graph-controlled grammars, programmed grammars, and matrix grammars by also counting, in addition, the number of nonterminal symbols that are actually used in the appearance checking mode. We prove that every recursively enumerable language can be generated by a graph-controlled grammar with only two nonterminal symbols when both symbols are used in the appearance checking mode. This result immediately implies that programmed grammars with three nonterminal symbols where two of them are used in the appearance checking mode as well as matrix grammars with three nonterminal symbols all of them used in the appearance checking mode are computationally complete. Moreover, we prove that matrix grammars with four nonterminal symbols with only two of them being used in the appearance checking mode are computationally complete, too. On the other hand, every language is recursive if it is generated by a graph-controlled grammar with an arbitrary number of nonterminal symbols but only one of the nonterminal symbols being allowed to be used in the appearance checking mode. This implies, in particular, that the result proving the computational completeness of graph-controlled grammars with two nonterminal symbols and both of them being used in the appearance checking mode is already optimal with respect to the overall number of nonterminal symbols as well as with respect to the number of nonterminal symbols used in the appearance checking mode, too. Finally, we also investigate in more detail the computational power of several language families which are generated by graph-controlled, programmed grammars or matrix grammars, respectively, with a very small number of nonterminal symbols and therefore are proper subfamilies of the family of recursively enumerable languages. |
Year | Venue | Keywords |
|---|---|---|
2007 | Journal of Automata, Languages and Combinatorics | nonterminal complexity,graph-controlled grammar,nonterminal symbol,overall number,recursively enumerable language,programmed grammar,arbitrary number,matrix grammar,small number,appearance checking mode |
Field | DocType | Volume |
Tree-adjoining grammar,Context-sensitive grammar,Rule-based machine translation,Terminal and nonterminal symbols,Discrete mathematics,Combinatorics,Context-free grammar,L-attributed grammar,Recursively enumerable language,Indexed grammar,Mathematics | Journal | 12 |
Issue | Citations | PageRank |
1 | 15 | 1.01 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Fernau | 1 | 1646 | 162.68 |
| Rudolf Freund | 2 | 1000 | 109.64 |
| Marion Oswald | 3 | 320 | 30.27 |
| Klaus Reinhardt | 4 | 136 | 9.74 |