An axiomatic definition of context-free rewriting and its application to NLC graph grammars (Q1102759)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4051025
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An axiomatic definition of context-free rewriting and its application to NLC graph grammars |
scientific article; zbMATH DE number 4051025 |
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
0 references
0.88536125
0 references
0 references
