Adaptive star grammars and their languages
| Autor: | Dirk Janssens, Berthold Hoffmann, Frank Drewes, Mark Minas |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Theoretical computer science
General Computer Science Computer science Programming language Deterministic context-free grammar Context-free language Context-sensitive grammar Linguistics Context-free grammar computer.software_genre Graph grammar Embedded pushdown automaton Theoretical Computer Science Tree-adjoining grammar TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Node cloning Rule-based machine translation Confluence Stochastic context-free grammar Context-free graph language L-attributed grammar Graph parsing computer c-command Computer Science(all) |
| Zdroj: | Theoretical computer science |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2010.04.038 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect