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

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Graph expressions and graph rewritings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Equivalences and transformations of regular systems - applications to recursive program schemes and grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4205068 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3785987 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4194478 / rank
 
Normal rank
Property / cites work
 
Property / cites work: IO and OI. II / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4179852 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two Families of Languages Related to ALGOL / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3774975 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decision problems for node label controlled graph grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3316615 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Neighborhood-uniform NLC grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3714485 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algebraic automata and context-free sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph theoretic closure properties of the family of boundary NLC graph languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Boundary NLC graph grammars—Basic definitions, normal forms, and complexity / rank
 
Normal rank

Latest revision as of 16:16, 18 June 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