TABLE-DRIVEN CONTEXT-FREE PICTURE GRAMMARS
| Autor: | Charita Bhika, Ryan Schwartz, Sigrid Ewert, Mutahi Waruhiu |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
business.industry
Context-sensitive grammar Context-free grammar computer.software_genre Picture language Tree-adjoining grammar Computer Science (miscellaneous) Indexed grammar Artificial intelligence Definite clause grammar L-attributed grammar Phrase structure grammar business computer Natural language processing Mathematics |
| Zdroj: | International Journal of Foundations of Computer Science. 18:1151-1160 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054107005194 |
| Popis: | Random context picture grammars (rcpgs) are a method of syntactic picture generation. The productions of such a grammar are context-free, but their application is regulated—permitted or forbidden—by context randomly distributed in the developing picture. In previous work we studied three natural subclasses of rcpgs, namely context-free picture grammars (cfpgs), random permitting context picture grammars (rPcpgs) and random forbidding context picture grammars (rFcpgs). We now introduce the notion of table-driven context-free picture grammars (Tcfpgs), and compare them to the above subclasses. We show that Tcfpgs are more powerful than cfpgs, and that they can generate a picture set (more commonly known as a gallery) that rPcpgs cannot. We present two conditions necessary for a gallery to be generated by a Tcfpg, and use these results to find two galleries that cannot be made by any Tcfpg. The second of these galleries can be generated by an rFcpg. Since it is easily shown that any gallery generated by a Tcfpg can be generated by an rFcpg, we can conclude that Tcfpgs are strictly weaker than rFcpgs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|