Home » forums » LtU Forum

Context free grammar for shapes in a 2d grid?

I was playing around with defining grammar productions rules for shapes in a 2d grid. Seems like using this type of scheme to generate complex shapes is very easy. But going the opposite direction and recognizing the language is impossible. If one has a grid consisting of cells filled with all terminal characters, if an arbitrary cell is chosen and the attempt is made to derive a parse tree from this cell, the ambiguity mounts quickly. Basically, any cell picked will give a different parse tree.

Thinking about it, this approach should generalize to grammars applied to graphs. Googling about for a bit and viewing the bibliograph statistics shows that there was some work done in this area in the late 90's but has since entirely disappeared:

Bibligraph stats for "graph grammar"

So, is anyone familiar with this area? Why did work in this area (almost) completely stop? Looks like some work was oriented toward parsing visual programming languages...

By markt at 2008-04-10 01:11 | LtU Forum | previous forum topic | next forum topic | other blogs | 5865 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Picture Languages

Sorry for the time to respond: didn't notice the post at first... I did some work a while ago with graph grammars, though I'm not terribly up to date these days.

My impression is that graph grammars as a field is doing very well (see, eg. the forthcoming ICGT 2008) , but picture languages as a subfield does seem to have become less active. I note the page you link to is to a bibliography assembled entirely by Frank Drewes, which I guess suggests the bibliography might be tilted towards picture languages & be less representative of graph grammars as a whole. I guess the impression of stasis is increased by the absence of major survey articles since the Handbook of Graph Grammars.

I did notice Drewes' book: Grammatical Picture Generation, might be your thing...

Edit: fixed missing text from above.

By Charles Stewart at Thu, 2008-04-10 09:12 | login or register to post comments

Grammatical Picture Generation

Dropped in to mention "Grammatical Picture Generation" by Drewes as well, in fact, if I recall and interpret things correctly the line of questioning posed in the original post (the membership problem in context-free grid picture languages) is thoroughly explored in section 5.1 of the book. I'll try to remember to check through the chapter when I get home tonight.

By Martin Berglund at Fri, 2008-04-11 08:15 | login or register to post comments

tree grammars

I don't know about general graph grammars, but tree grammars and tree automata are very much alive and kicking, and, surprisingly (to me), increasingly relevant.

By lmeyerov at Fri, 2008-04-11 06:37 | login or register to post comments

Applications of tree grammars

It's been my impression that, while tree grammars can be applied as picture languages, most of their applications lie elsewhere. Johanna Hogberg's thesis from last year, Contributions to the theory and applications of tree languages has as its main application areas bisimulation minimisation, music generation and machine learnability. Is my impression that other areas like these are more lively areas of research right, I wonder?

By Charles Stewart at Fri, 2008-04-11 11:35 | login or register to post comments