The monadic second-order logic of graphs. I. Recognizable sets of finite graphs

1990/03/01 by Bruno Courcelle · 29 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Computer science #Context (archaeology) #Decidability #Description logic #Discrete mathematics #Finite set #Graph #Higher-order logic #Logic, Reasoning, and Knowledge #Mathematics #Maximal independent set #Monadic predicate calculus #Order (exchange) #Set (abstract data type) #Theoretical computer science #semigroups and automata theory

paper · pdf · doi:10.1016/0890-5401(90)90043-h

crossref issued 1990/03/01 · crossref published 1990/03/01 · crossref published-print 1990/03/01 · openalex publication_date 1990/03/01 · crossref created 2004/12/02 · crossref deposited 2019/02/01 · openalex created_date 2025/10/10 · crossref indexed 2026/08/01 · openalex updated_date 2026/08/03

Citations

• The structure of the models of decidable monadic theories of graphs

Cited by

• Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
• A c^k n 5-Approximation Algorithm for Treewidth
• Finding All Leftmost Separators of Size ≤ k
• An Improvement of Reed’s Treewidth Approximation
• Finding approximate separators and computing tree width quickly
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth
• Large Induced Subgraphs via Triangulations and CMSO
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Grad and classes with bounded expansion II. Algorithmic aspects
• Approximating treewidth and pathwidth of some classes of perfect graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Twin-width VIIIa: Delineation
• A Congestion Parameter for Depth-First Graph Traversals
• Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
• Completely Independent Steiner Trees
• Quickly excluding an annotated planar graph
• Secure Domination in Bisplit graphs -- A Structural and algorithmic study
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion
• Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics
• Branch-depth: Generalizing tree-depth of graphs
• Splitting a graph into disjoint induced paths or cycles
• MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree k-Outerplanar Graphs
• Logics for Unranked Trees: An Overview
• Temporal Graph Realization With Bounded Stretch
• Recognizable Graph Languages for Checking Invariants
• Characterizing width two for variants of treewidth
• Parameterized Modal Satisfiability
• Structural Decompositions of Epistemic Logic Programs
• Treewidth [wikipedia]