| Publication type: |
Article |
| Author: |
Drewes, Frank, Hoffmann, Berthold, Janssens, Dirk, Minas, Mark |
| Title: |
Adaptive Star Grammars and Their Languages |
| Volume: |
411 |
| Page(s): |
3090 – 3109 |
| Journal: |
Theoretical Computer Science |
| Year published: |
2010 |
| Abstract: |
Motivated by applications that require mechanisms for describing the structure of object-oriented programs, adaptive star grammars are introduced, and their fundamental properties are studied. In adaptive star grammars, rules are actually schemata which, via the cloning of so-called multiple nodes, may adapt to potentially infinitely many contexts when they are applied. This mechanism makes adaptive star grammars more powerful than context-free graph grammars. Nevertheless, they turn out to be restricted enough to share some of the basic characteristics of context-free devices. In particular, the underlying substitution operator enjoys associativity and confluence properties quite similar to those of context-free graph grammars, and the membership problem for adaptive star grammars is decidable. |
| Internet: |
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-501071F-2&_user=963894&_coverDate=07%2F17%2F2010&_rdoc=9&_fmt=high&_orig=browse&_origin=browse&_zone=rslt_list_item&_srch=doc-info%28%23toc%235674%232010%23995889965%232197811%23FLP%23display% |
| PDF Version: |
http://www.informatik.uni-bremen.de/~hof/papers/asgl.pdf |
| Status: |
Reviewed |
| Last updated: |
25. 11. 2010 |
|
 |
