Back to University of Twente portal
Regularly Controlled Bidirectional Extended Linear Basic Grammars (Revised and extended version)
Hogendorp, Jan Anne (1989) Regularly Controlled Bidirectional Extended Linear Basic Grammars (Revised and extended version). [Report]
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 151Kb |
| Abstract: | We study the concept of bidirectional application of productions - i.e., using a production of a grammar as a reduction too - with respect to regularly controlled extended linear basic (macro) grammars [3], provided with a restricted mode of derivation. So this new grammatical model is in essence equal to the regularly controlled bidirectional context-free grammar of [15] in which the underlying context-free grammar is replaced by an extended linear basic grammar. We establish closure properties of the corresponding family of languages; viz. for the outside-in or OI mode we obtain a full substitution-closed AFL, and for the inside-out or IO mode we obtain a full QAFL closed under deterministic substitution. The notion of bidirectionality gives rise to a dramatic increase of generating power; even under minor assumptions the OI [IO] instance of such grammars generate all OI-macro [IO-macro, respectively] languages. Furthermore, in case of free application of productions and reductions we obtain a generating capacity equal to the one of phrase-structure grammars. |
| Item Type: | Report |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/64295 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page