Recognizable sets of graphs: equivalent definitions and closure properties

DOI10.1017/S0960129500000359zbMath0798.68090OpenAlexW2027893394MaRDI QIDQ4286529

Bruno Courcelle

Publication date: 26 April 1994

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0960129500000359

zbMATH Keywords

recognizability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42)

Related Items

The monadic second-order logic of graphs. X: Linear orderings, Recognizable sets of graphs of bounded tree-width, A confluent reduction for the λ-calculus with surjective pairing and terminal object, Basic notions of universal algebra for language theory and graph grammars, The definition in monadic second-order logic of modular decompositions of ordered graphs, Recognizability, hypergraph operations, and logical types, Unnamed Item, The recognizability of sets of graphs is a robust property

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• A comparison of compatible, finite, and inductive graph properties
• Handle-rewriting hypergraph grammars
• Easy problems for tree-decomposable graphs
• Graph expressions and graph rewritings
• Algebraic automata and context-free sets