| Publication type: |
Technical Report |
| Author: |
Drewes, Frank, Hoffmann, Berthold, Janssens, Dirk, Minas, Mark |
| Title: |
Adaptive Star Grammars and Their Languages |
| Number: |
2008-01 |
| Year published: |
2008 |
| Institution: |
Departement Wiskunde-Informatica, Universiteit Antwerpen |
| Type: |
Technical Report |
| 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.
|
| PDF Version: |
http://www.informatik.uni-bremen.de/~hof/papers/asgl.pdf |
| Keywords: |
graph grammar language adaptive star |
| Status: |
Other |
| Last updated: |
25. 08. 2009 |
|
 |
