Name
Abstract | ||
|---|---|---|
A 1S grammar generalizes a context-free grammar in the following way: a production A → α can be applied to a string uAv (to rewrite the designed occurence of A ) provided that all letters from u belong to a fixed alphabet X and all letters from v belong to a fixed alphabet Z (the alphabets X and Z are independent of the production). It is proved that a language is generated by a 1S grammar if and only if it is context-free: this solves an open problem from the theory of selective substitution grammars (Kleijn and Rozenberg, 1981/82). |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1016/0304-3975(85)90096-9 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
one sequential grammars,Selective substitution grammars,F.4.2,F.4.3,context-free languages | Journal | 37 |
Issue | ISSN | Citations |
3 | 0304-3975 | 1 |
PageRank | References | Authors |
0.36 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Ehrenfeucht | 1 | 1823 | 497.83 |
| H.C.M. Kleijn | 2 | 9 | 3.29 |
| G. Rozenberg | 3 | 396 | 45.34 |