×
Courcelle, B.

An axiomatic definition of context-free rewriting and its application to NLC graph grammars. (English) Zbl 0644.68095

Theor. Comput. Sci. 55, 141-181 (1987).
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.
Reviewer: A.V.Anisimov

Cited in 3 Reviews
Cited in 60 Documents

MSC:

68Q45 Formal languages and automata
68R10 Graph theory (including graph drawing) in computer science

Keywords:

node-label controlled graph grammars; context-free grammar; NLC; monadic second-order theory; decidability

Software:

ALGOL 60
PDF BibTeX XML Cite
\textit{B. Courcelle}, Theor. Comput. Sci. 55, 141--181 (1987; Zbl 0644.68095)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] M. Bauderon and B. Courcelle, Graph expressions and graph rewritings, Mathematical Systems Theory, to appear. · Zbl 0641.68115
[2] Courcelle, B., Equivalences and transformations of regular systems—applications to recursive program schemes and grammars, Theoret. comput. sci., 42, 1-122, (1986) · Zbl 0636.68104
[3] Courcelle, B., Recognizability and monadic second-order definability for sets of finite graphs, (), submitted for publication. · Zbl 0686.68011
[4] Courcelle, B., On context-free sets of graphs and their monadic second-order theory, (), to appear. · Zbl 0643.68105
[5] Ehrig, H., Introduction to the algebraic theory of graph grammars, (), 1-69
[6] Engelfriet, J.; Schmidt, E.; Engelfriet, J.; Schmidt, E., IO and OI, J. comput. system sci., J. comput. system sci., 16, 67-99, (1978) · Zbl 0371.68020
[7] Gécseg, F.; Steinby, M., Tree automata, (1984), Akadémiai Kiadó Budapest · Zbl 0396.68041
[8] Ginsburg, S.; Rice, H., Two families of languages related to ALGOL, J. ACM, 9, 350-371, (1962) · Zbl 0196.01803
[9] Habel, A.; Kreowski, H.J., Some structural aspects of hypergraph languages generated by hyperedge replacements, (), 207-219
[10] Huet, G., Confluent reduction: abstract properties and applications to term-rewriting systems, J. ACM, 27, 797-821, (1980) · Zbl 0458.68007
[11] Huet, G.; Oppen, D., Equations and rewrite rules, a survey, (), 349-405
[12] Janssens, D.; Rozenberg, G., Decision problems for NLC grammars, J. comput. system sci., 22, 144-177, (1981) · Zbl 0466.68067
[13] Janssens, D.; Rozenberg, G., A survey of NLC grammars, (), 114-128, L’Aquila · Zbl 0533.68069
[14] Janssens, D.; Rozenberg, G., Neighborhood-uniform NLC grammars, Comput. vis., graphics image process, 35, 131-151, (1986) · Zbl 0624.68061
[15] Kaul, M., Syntaxanalyse von graphen bei praezedenz-graph-grammatiken, () · Zbl 0587.68076
[16] Mezei, J.; Wright, J., Algebraic automata and context-free sets, Inform, and control, 11, 3-29, (1967) · Zbl 0155.34301
[17] Rozenberg, G.; Welzl, E., Graph-theoretic closure properties of the family of boundary NLC graph languages, Acta inform., 23, 289-309, (1986) · Zbl 0606.68070
[18] Rozenberg, G.; Welzl, E., Boundary NLC grammars—basic definitions, normal forms and complexity, Inform. and control, 69, 136-167, (1986) · Zbl 0608.68060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.