The recognizability of sets of graphs is a robust property

DOI10.1016/j.tcs.2005.03.018zbMath1077.68070arXivcs/0609109OpenAlexW2170244924MaRDI QIDQ2566292

Bruno Courcelle, Pascal Weil

Publication date: 22 September 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0609109

zbMATH Keywords

Modular decompositionGraph algebraHyperedge replacementLocally finite congruenceQuantifier-free definable operationRecognizable set of graphsVertex replacement

Mathematics Subject Classification ID

Formal languages and automata (68Q45) 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 (9)

Simple monadic theories and partition width ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Recognizable languages of arrows and cospans ⋮ Graph Operations Characterizing Rank-Width and Balanced Graph Expressions ⋮ A syntactic congruence for languages of birooted trees ⋮ Syntactic recognizability of graphs with fuzzy attributes ⋮ Algebraic recognizability of regular tree languages ⋮ Recognizability, hypergraph operations, and logical types ⋮ Graph operations characterizing rank-width

Cites Work

• Algorithmic uses of the Feferman-Vaught theorem
• Basic notions of universal algebra for language theory and graph grammars
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The monadic theory of order
• Modular decomposition and transitive orientation
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• \(k\)-NLC graphs and polynomial algorithms
• Monadic second-order definable text languages
• The monadic second-order logic of graphs. X: Linear orderings
• Series-parallel languages and the bounded-width property
• Rationality in algebras with a series operation
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Towards a language theory for infinite N-free pomsets.
• The complexity of first-order and monadic second-order logic revisited
• Regular sets of infinite message sequence charts
• Structural properties of context-free sets of graphs generated by vertex replacement
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Recognizability, hypergraph operations, and logical types
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The first order properties of products of algebraic systems
• An algebraic theory of graph reduction
• Recognizable sets of graphs: equivalent definitions and closure properties
• Handbook of Graph Grammars and Computing by Graph Transformation
• Mathematical Foundations of Computer Science 2004
• Algebraic automata and context-free sets
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Developments in Language Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The recognizability of sets of graphs is a robust property