Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-03T05:37:17.175Z Has data issue: false hasContentIssue false
  • English
  • Français

Recognizable sets of graphs: equivalent definitions and closure properties

Published online by Cambridge University Press:  04 March 2009

Bruno Courcelle
Bruno Courcelle
Affiliation:
Bordeaux-1 University, LaBRI (CNRS Laboratory no 1304), 351 Cours de la Libération, 33405 Talence, France. ([email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The notion of a recognizable set of words, trees or graphs is relative to an algebraic structure on the set of words, trees or graphs respectively. We establish that several algebraic structures yield the same notion of a recognizable set of graphs. This notion is equivalent to that of a fully cutset-regular set of graphs introduced by Fellows and Abrahamson. We also establish that the class of recognizable sets of graphs is closed under the operations considered in these various equivalent definitions. This fact is not a standard consequence of the definition of recognizability.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 4 , Issue 1 , March 1994 , pp. 1 - 32
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abrahamson, K. and Fellows, M. (1993) Finite automata, bounded tree-width and wellquasiordering. In: Robertson, N. and Seymour, P. (eds.) Graph structure theory. Contemporary Mathematics 147 539–564.CrossRefGoogle Scholar
Arnborg, S., Courcelle, B., Proskurowski, A. and Seese, D. (1991a) An algebraic theory of graph reduction. Report 91–36, Bordeaux-1 University. (Short version in Springer- Verlag Lecture Notes in Computer Science 532 70–83; full paper to appear in J. ACM.)CrossRefGoogle Scholar
Arnborg, S., Lagergren, J. and Seese, D. (1991b) Easy problems for tree decomposable graphs. J. of Algorithms 12 308–340.CrossRefGoogle Scholar
Arnold, A. and Niwinski, D. (1992) Fixed point characterization of weak monadic logic definable sets of trees. In: Nivat, M. and Podelski, A. (eds.) Tree automata and languages, Elsevier159–188.Google Scholar
Bauderon, M. and Courcelle, B. (1987) Graph expressions and graph rewritings. Mathematical Systems Theory 20 83–127.CrossRefGoogle Scholar
Courcelle, B. (1986) Equivalences and transformations of regular systems. Applications to recursive program schemes and grammars. Theor. Comp. Sci. 42 1–122.CrossRefGoogle Scholar
Courcelle, B. (1987) An axiomatic definition of context-free rewriting and its application to NLC graph grammars. Theor. Comput. Sci. 55 141–181.CrossRefGoogle Scholar
Courcelle, B. (1989) On Recognizable sets and tree automata. In: Nivat, M. and Ait-Kaci, H. (eds.) Resolution of equations in Algebraic Structures, Vol. 1, Academic Press 93–126.Google Scholar
Courcelle, B. (1990a) The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation 85 12–75.Google Scholar
Courcelle, B. (1990b) Graph rewriting: An algebraic and logic approach. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume B, Elsevier, 193–242.Google Scholar
Courcelle, B. (1991) The monadic second-order logic of graphs V: On closing the gap between definability and recognizability. Theor. Comp. Sci. 80 153–202.CrossRefGoogle Scholar
Courcelle, B. (1992) The monadic second order logic of graphs VII: Graph as relational structures. Theor. Comp. Sci. 101 3–33.CrossRefGoogle Scholar
Courcelle, B. (1993) Graph grammars, monadic second-order logic and the theory of graph minors. In: Robertson, N. and Seymour, P. (eds.) Graph structure theory. Contemporary Mathematics 147 565–590.Google Scholar
Courcelle, B., Engelfriet, J. and Rozenberg, G. (1993) Handle-rewriting hypergraph grammars. J. Comput. System. Sci. 46 218–270.CrossRefGoogle Scholar
Courcelle, B. and Lagergren, J. (1992). Recognizable sets of graphs of bounded tree-width. Report 92–68, Bordeaux-1 University. (Springer-Verlag Lecture Notes in Computer Science, to appear).Google Scholar
Ehrig, H. and Mahr, B. (1985) Fundamentals of algebraic specifications I, Springer-Verlag.CrossRefGoogle Scholar
Eilenberg, S. (1974). Automata, languages and machines, Vol. A, Academic Press, New York.Google Scholar
Fellows, M. and Abrahamson, K. (1993) Cutset-regularity beats well-quasi ordering for bounded treewidth. In: Seymour, P. and Robertson, N. (eds.) Proceedings of the Graph Minors Conference, AMS.Google Scholar
Gegsec, F. and Steinby, M. 1984 Tree automata, Akademiai Kiado, Budapest.Google Scholar
Habel, A. (1992) Hyperedge replacement: grammar and languages. Springer-Verlag Lecture Notes In Computer Science. 643.Google Scholar
Habel, A., Kreowski, H.-J. and Lautemann, C. (1993) A comparison of compatible, finite and inductive graph properties. Theor. Comp. Sci. 110 145–168.CrossRefGoogle Scholar
Lengauer, T. and Wanke, E. (1988) Efficient analysis of graph properties on context-free graph languages, Proceedings ICALP '88. Springer-Verlag Lecture Notes in Computer Science 317 379–393.CrossRefGoogle Scholar
Mezei, J. and Wright, J. (1967) Algebraic automata and context-free sets. Information and Control 11 3–29.CrossRefGoogle Scholar
Wechler, W. (1991) Universal algebra for computer scientists. Springer-Verlag.Google Scholar
Wirsing, M. (1990) Algebraic specifications. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume B, Elsevier675–779.Google Scholar