As a direct continuation of the earlier research on conjunctive grammars - context-free grammars equipped with intersection - this paper introduces a new class of formal grammars, which allow the use of all set-theoretic operations as an integral part of the formalism of rules. Rigorous semantics for such grammars is defined by language equations in a way that allows to generalize some techniques from the theory of context-free grammars, including Chomsky normal form, Cocke-Kasami-Younger recognition algorithm and some limited extension of the notion of a parse tree, which together allow to conjecture the practical applicability of the new concept.
| Original language | English |
|---|---|
| Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Editors | Zoltan Esik, Zoltan Fulop |
| Publisher | Springer Nature |
| Pages | 398-410 |
| Number of pages | 13 |
| ISBN (Electronic) | 3540404341, 9783540404347 |
| DOIs | |
| State | Published - 2003 |
| Externally published | Yes |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2710 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
ID: 78926202