An axiomatic definition of context-free rewriting and its application to NLC graph grammars (Q1102759): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: Publication / rank | |||
Normal rank | |||
Revision as of 03:13, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An axiomatic definition of context-free rewriting and its application to NLC graph grammars |
scientific article |
Statements
An axiomatic definition of context-free rewriting and its application to NLC graph grammars (English)
0 references
1987
0 references
The paper deals with graph grammars. An abstract notion of context-free grammar over an arbitrary class of combinatorial objects is introduced. The node-label controlled (NLC) graph grammars, which have been defined and investigated by Janssens, Rozenberg and Welzl, are studied from this point of view. A monadic second-order theory of context-free NLC sets of graphs appropriate for expressing properties of graphs is introduced. It is shown that this theory is decidable. Some decidability results of graph grammars obtained by other authors are simple consequences of this result.
0 references
node-label controlled graph grammars
0 references
context-free grammar
0 references
NLC
0 references
monadic second-order theory
0 references
decidability
0 references
