A HIERARCHY RESULT FOR RANDOM FORBIDDING CONTEXT PICTURE GRAMMARS
| Autor: | Sigrid Ewert, Andries P. J. van der Walt |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
business.industry
Computer science Context-sensitive grammar Context-free grammar Embedded pushdown automaton Tree-adjoining grammar Artificial Intelligence Indexed grammar Computer Vision and Pattern Recognition Definite clause grammar Artificial intelligence L-attributed grammar Phrase structure grammar business Software |
| Zdroj: | International Journal of Pattern Recognition and Artificial Intelligence. 13:997-1007 |
| ISSN: | 1793-6381 0218-0014 |
| DOI: | 10.1142/s0218001499000550 |
| Popis: | We use random context picture grammars to generate pictures through successive refinement. 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. Grammars using this relatively weak context often succeed where context-free grammars fail, e.g. in generating the Sierpiński carpets. On the other hand it proved possible to develop iteration theorems for three subclasses of these grammars, namely a pumping–shrinking, a pumping and a shrinking lemma for context-free, random permitting and random forbidding context picture grammars, respectively. Finding necessary conditions is problematic in the case of most models of context-free grammars with context-sensing ability, since they consider a variable and its context as a finite connected array. We have already shown that context-free picture grammars are strictly weaker than both random permitting and random forbidding context picture grammars, also that random permitting context is strictly weaker than random context. We now show that grammars which use forbidding context only are strictly weaker than random context picture grammars. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|