×
Bauderon, Michel

Infinite hypergraphs. I: Basic properties. (English) Zbl 0758.05069

Theor. Comput. Sci. 82, No. 2, 177-214 (1991).
Some properties of the category of infinite directed hyperedge-labelled hypergraphs are studied in this paper. An algebraic structure is introduced to describe such hypergraphs by means of infinite expressions. It is also shown that two expressions define the same hypergraph if and only if they are congruent with respect to some rewriting system. These results are applied in solving systems of recursive equations on hypergraphs.
Reviewer: C.-Q.Zhang (Morgantown)

Cited in 1 Review
Cited in 7 Documents

MSC:

05C65 Hypergraphs
18A15 Foundations, relations to logic and deductive systems

Keywords:

infinite hypergraphs
PDF BibTeX XML Cite
\textit{M. Bauderon}, Theor. Comput. Sci. 82, No. 2, 177--214 (1991; Zbl 0758.05069)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Adamek, J.; Koubek, V., Least fixed points of a functor, J. Comput. System Sci., 19, 163-178 (1979) · Zbl 0423.18007
[2] Bauderon, M., On some properties of infinite graphs, (Proc. WG’88. Proc. WG’88, Lecture Notes in Computer Science, 344 (1989), Springer: Springer Berlin), 54-73, Amsterdam
[4] Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. Systems Theory, 20, 83-127 (1987) · Zbl 0641.68115
[5] Caucal, D., Pattern graphs, (Research report 441 (1988), IRISA) · Zbl 0992.68157
[6] Coquand, T., Categories of embedding, Theoret. Comput. Sci., 68, 221-237 (1989) · Zbl 0688.18004
[7] Coquand, T.; Ehrart, T., An equational presentation of higher-order logic, (Category Theory and Computer Science. Category Theory and Computer Science, Lecture Notes in Computer Science, 283 (1987), Springer: Springer Berlin), 40-56, Edinburgh
[8] Courcelle, B., Frontiers of infinite trees, RAIRO Inform. Théor., 12, 4, 319-337 (1978) · Zbl 0411.68065
[9] Courcelle, B., Fundamental properties of trees, Theoret. Comput. Sci., 25, 95-169 (1983) · Zbl 0521.68013
[10] Courcelle, B., The monadic 2nd order logic of graphs IV: definability properties of equational graphs, Ann. Pure Appl. Logic, 193-255 (1990) · Zbl 0731.03006
[12] Courcelle, B., Graph rewriting: an algebraic and logic approach, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. B (1990), Elsevier: Elsevier Amsterdam), 193-242 · Zbl 0900.68282
[13] Dauchet, M.; Timmerman, E., Continuous monoids and yields of infinite trees, RAIRO Inform. Théor., 20, 3, 251-274 (1986) · Zbl 0605.06012
[14] Ehrig, H., Introduction to the Algebraic Theory of Graphs, (Lecture Notes in Computer Science, 73 (1977), Springer: Springer Berlin), 1-69
[15] Ehrig, H.; Mahr, B., Fundamentals of algebraic specifications, (EATCS Monographs in Theoretical Computer Science (1985), Springer: Springer Berlin) · Zbl 0557.68013
[16] Goguen, J. A.; Burstall, R. M., Some fundamental algebraic tools for the semantics of computation, Theoret. Comput. Sci. Part 2, 31, 263-295 (1984) · Zbl 0566.68066
[17] Habel, A., Hyperedge replacement grammars and language, Thesis (1989), Bremen
[18] (May we introduce to you: hyperedge replacement. May we introduce to you: hyperedge replacement, Lecture Notes in Computer Science, 291 (1987), Springer: Springer Berlin), 15-26 · Zbl 0643.68106
[19] Heilbrunner, S., An algorithm for the solution of fixed point equations for infinite words, RAIRO Inform. Théor., 14, 131-141 (1980) · Zbl 0433.68062
[20] Kanda, A., Fully effective solutions of recursive domain equations, (MFCS 1979. MFCS 1979, Lecture Notes in Computer Science, 74 (1979), Springer: Springer Berlin), 326-336
[21] Lambek, J., A fixpoint theorem for complete category, Math. Z., 103, 151-161 (1968) · Zbl 0149.26105
[22] Lambek, J., Fixpoint revisited, Logik at Botik, (Lecture Notes in Computer Science, 363 (1989), Springer: Springer Berlin), 200-207
[23] Lehmann, D. J., Categories for fixpoint semantics, 17th Symp. on Foundations of Computer Science, 122-126 (1976), Houston
[24] Lehmann, D. J.; Smyth, M. B., Algebraic specification of data types, Math. Systems Theory, 14, 97-139 (1981) · Zbl 0457.68035
[25] Lindenmayer, A., Models for multicellular development: characterization, inference and complexity of \(L\)-systems, (Trends, Techniques and Problems in Theoretical Computer Science. Trends, Techniques and Problems in Theoretical Computer Science, Lecture Notes in Computer Science, 281 (1987), Springer: Springer Berlin), 138-168 · Zbl 0648.92002
[26] Manes, E., Algebraic Theories (1976), Springer: Springer Berlin · Zbl 0353.18007
[27] Manes, E.; Arbib, M., Algebraic Approach to Program Semantics, (The AKM Series in Theoretical Computer Science (1986), Springer: Springer Berlin) · Zbl 0414.68055
[28] McLane, S., Category for the Working Mathematician (1971), Springer: Springer Berlin
[29] Muller, D.; Schupp, P., The theory of ends, pushdown automata and second-order logic, Theoret. Comput. Sci., 37, 51-75 (1985) · Zbl 0605.03005
[30] Smyth, M. B., Powerdomains, J. Comput. Systems Sci., 16, 23-36 (1978) · Zbl 0408.68017
[31] Smyth, M. B., Computability in categories, (Proc. 7th ICALP. Proc. 7th ICALP, Lecture Notes in Computer Science, 85 (1980), Springer: Springer Berlin), 609-620 · Zbl 0471.68031
[32] Smyth, M. B.; Plotkin, G., The category theoretic solution to recursive domain equations, SIAM J. Comput., 11, 4 (1982) · Zbl 0493.68022
[33] Thomas, W., On frontier of regular trees, RAIRO Inform. Théor., 20, 4, 371-381 (1986) · Zbl 0639.68071
[34] Weihrauch, K., Computability, (EATCS Monographs in Theoretical Computer Science (1986), Springer: Springer Berlin) · Zbl 0611.03002
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.