An axiomatic definition of context-free rewriting and its application to NLC graph grammars (Q1102759): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Changed an Item
Property / describes a project that uses
 
Property / describes a project that uses: ALGOL 60 / rank
 
Normal rank

Revision as of 14:11, 29 February 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
    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

    Identifiers