|
Title
|
|
|
|
Adaptive star grammars and their languages
| |
|
Author
|
|
|
|
| |
|
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. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
Theoretical computer science. - Amsterdam
| |
|
Publication
|
|
|
|
Amsterdam
:
2010
| |
|
ISSN
|
|
|
|
0304-3975
| |
|
DOI
|
|
|
|
10.1016/J.TCS.2010.04.038
| |
|
Volume/pages
|
|
|
|
411
:34/36
(2010)
, p. 3090-3109
| |
|
ISI
|
|
|
|
000280276200008
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|