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

DOI10.1016/0890-5401(90)90043-HzbMath0722.03008OpenAlexW2028357390MaRDI QIDQ2641288

No author found.

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90043-h

zbMATH Keywords

decidability recognition definability formal languages universal algebra context-free set many-sorted algebra of graphs monadic second-order logic of graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70) Structural characterization of families of graphs (05C75) Decidability of theories and sets of sentences (03B25)

Related Items (only showing first 100 items - show all)

An algorithmic metatheorem for directed treewidth ⋮ Compatibility of unrooted phylogenetic trees is FPT ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity ⋮ Compactors for parameterized counting problems ⋮ A linear time algorithm for metric dimension of cactus block graphs ⋮ Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ Computing the zig-zag number of directed graphs ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Structural parameterizations for boxicity ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ On the feedback vertex set polytope of a series-parallel graph ⋮ Between treewidth and clique-width ⋮ Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry ⋮ An asymptotic analysis of labeled and unlabeled \(k\)-trees ⋮ Recognizability equals definability for graphs of bounded treewidth and bounded chordality ⋮ Planar disjoint-paths completion ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ The VC-dimension of graphs with respect to \(k\)-connected subgraphs ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Kernelization using structural parameters on sparse graph classes ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Characterizing width two for variants of treewidth ⋮ Algorithmic aspects of open neighborhood location-domination in graphs ⋮ XML schema, tree logic and sheaves automata ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Increasing the minimum degree of a graph by contractions ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Kernel bounds for path and cycle problems ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Optimization problems in dotted interval graphs ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Are there any good digraph width measures? ⋮ Meta-kernelization with structural parameters ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Complexity of total outer-connected domination problem in graphs ⋮ Directed elimination games ⋮ The complexity of two graph orientation problems ⋮ On low tree-depth decompositions ⋮ Injective colorings with arithmetic constraints ⋮ Tree-width of hypergraphs and surface duality ⋮ Model-checking hierarchical structures ⋮ Distance three labelings of trees ⋮ On graph contractions and induced minors ⋮ On the model-checking of monadic second-order formulas with edge set quantifications ⋮ Decomposition width of matroids ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ A combinatorial optimization algorithm for solving the branchwidth problem ⋮ Contracting planar graphs to contractions of triangulations ⋮ Quadratic kernelization for convex recoloring of trees ⋮ The dag-width of directed graphs ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ On rules with existential variables: walking the decidability line ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ Confronting intractability via parameters ⋮ Cycle-maximal triangle-free graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Spanners in sparse graphs ⋮ Approximation algorithms for intersection graphs ⋮ The string generating power of context-free hypergraph grammars ⋮ The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability ⋮ A regular characterization of graph languages definable in monadic second-order logic ⋮ Complexity of conflict-free colorings of graphs ⋮ A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Algorithms for decision problems in argument systems under preferred semantics ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ The monadic second-order logic of graphs. IX: Machines and their behaviours ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ The monadic second-order logic of graphs. VII: Graphs as relational structures ⋮ On first-order definitions of subgraph isomorphism properties ⋮ On the path-width of integer linear programming ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Recursively indefinite databases ⋮ Efficient computation of the characteristic polynomial of a tree and related tasks ⋮ Partitioning graphs of supply and demand ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Complexity of secure sets ⋮ Fast compatibility testing for rooted phylogenetic trees ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width ⋮ Complexity of conditional colorability of graphs ⋮ Treewidth and logical definability of graph products ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ On the treewidth of dynamic graphs ⋮ Juggrnaut: using graph grammars for abstracting unbounded heap structures ⋮ Recursive queries and context-free graph grammars ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ The parameterized complexity of the induced matching problem ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ Induced packing of odd cycles in planar graphs ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ The monadic second-order logic of graphs. IV: Definability properties of equational graphs ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs

Cites Work

This page was built for publication: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs