 Generic
Number - 522 |
| References
- 13 |
| Written
Date -
September 7th, 06 |
| Modified
Date -
September 7th, 06 |
| Downloaded
Counts - 113 |
| Visited
Counts - 1340 |
| |
| Original
File |
|
|
|
| Summary |
Programmed grammars, one of the most important and well investigated classes of
grammars with context-free rules and a mechanism controlling the application of the
rules, can be described by graphs. We investigate whether or not the restriction to
special classes of graphs restricts the generative power of programmed grammars
with erasing rules and without appearance checking, too. We obtain that Eulerian,
Hamiltonian, planar and bipartite graphs and regular graphs of degree at least three
are pr-universal in that sense that any language which can be generated
by programmed grammars (with erasing rules and without appearance checking)
can be obtained by programmed grammars where the underlying graph belongs to
the given special class of graphs, whereas complete graphs, regular graphs of
degree 2 and backbone graphs lead to proper subfamilies of the family
of programmed languages.
|
|
The power of programmed grammars \\ with graphs from various classes
