×

zbMATH — the first resource for mathematics

The monadic second-order logic of graphs. VII: Graphs as relational structures. (English) Zbl 0809.03006
[Part VI is reviewed above.]
The author defines operations on stuctures that are compatible with monadic second-order logic and that are powerful enough to represent context-free graph and hypergraph grammars of various types, namely, the so-called hyperedge replacement, C-edNCE, and separated handle rewriting grammars. Several results concerning monadic second-order properties of the generated sets are obtained in a uniform way.
Reviewer: Li Xiang (Guiyang)

MSC:
03B15 Higher-order logic; type theory (MSC2010)
05C99 Graph theory
68Q42 Grammars and rewriting systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. algorithms, 12, 308-340, (1991) · Zbl 0734.68073
[2] Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. system theory, 20, 83-127, (1987) · Zbl 0641.68115
[3] Courcelle, B., Equivalences and transformations of regular systems. applications to recursive program schemes and grammars, Theoret. comput. sci., 42, 1-22, (1986) · Zbl 0636.68104
[4] Courcelle, B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoret. comput. sci., 55, 141-181, (1987) · Zbl 0644.68095
[5] Courcelle, B., Graph rewriting: an algebraic and logic approach, (), 193-242 · Zbl 0900.68282
[6] Courcelle, B., The monadic second-order logic of graphs I. recognizable sets of finite graphs, Inform. and comput., 85, 12-75, (1990) · Zbl 0722.03008
[7] Courcelle, B., The monadic second-order logic of graphs V: on closing the gap between definability and recognizability, Theoret. comput. sci., 80, 153-202, (1991) · Zbl 0754.68065
[8] B.Courcelle, The monadic second-order logic of graphs VI: On several representations of graphs by relational structures, Discrete Applied Math.in press;see also 4th IEEE Symp. on Logic in Computer Science 1990, Philadelphia.
[9] Courcelle, B.; Engelfriet, J., A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars, () · Zbl 0830.68098
[10] B. Courcelle, J.Engelfriet and G.Rozenberg, Handle-rewriting hypergraph grammars, Parts I and II. Report 90-84 of Bordeaux-1 University, or reports 90-08 and 90-09 of University of Leiden; short version in: · Zbl 0765.68084
[11] Doner, J., Tree acceptors and some of their applications, J. comput. system sci., 4, 406-451, (1970) · Zbl 0212.02901
[12] Ehrig, H.; Kreowski, H.-J.; Maggiolo-Schettini, A.; Rosen, B.; Winkowski, J., Transformations of structures, an algebraic approach, Math. systems theory, 14, 305-334, (1981) · Zbl 0491.68035
[13] Engelfriet, J., A characterization of context-free NCE graph languages by monadic second-order logic on trees, (), 311-327 · Zbl 0765.68090
[14] Engelfriet, J.; Heyker, L., The string generating power of context-free hypergraph grammars, J. comput. system sci., 43, 328-360, (1991) · Zbl 0776.68075
[15] Engelfriet, J.; Rozenberg, G., A comparison of boundary graph grammars and context-free hypergraph grammars, Inform. and comput., 84, 163-206, (1990) · Zbl 0706.68067
[16] Gurevich, Y., Monadic second-order theories, (), 479-506
[17] Habel, A., Hyperedge replacement: grammars and languages, Doctoral dissertation, (1989), Bremen · Zbl 0787.68066
[18] Habel, A.; Kreowski, H.J., May we introduce to you: hyperedge replacement, Lecture notes in computer science, Vol. 291, 15-26, (1987) · Zbl 0643.68106
[19] Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 760-777, (1987) · Zbl 0634.68034
[20] Kannellakis, P., Elements of relational data base theory, (), 1073-1156
[21] Rabin, M., A simple method for undecidability proofs and some applications, (), 58-68
[22] Rabin, M., Decidability of second-order theories and automata on infinite trees, Trans. amer. math. soc., 141, 1-35, (1969) · Zbl 0221.02031
[23] Rabin, M., Decidable theories, (), 595-630
[24] 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.