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)

Monadic second-order definable graph transductions: a survey ⋮ Node replacements in embedding normal form. ⋮ The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions. ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ The complexity of connectivity problems on context-free graph languages ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ The monadic second order logic of graphs. VI: On several representations of graphs by relational structures ⋮ A recurrence template for several parameters in series-parallel graphs ⋮ The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ Regularity and locality in \(k\)-terminal graphs ⋮ Context-free graph languages of bounded degree are generated by apex graph grammars ⋮ The complexity of induced minors and related problems ⋮ Notes on complexity of packing coloring ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ On the complexity of rainbow coloring problems ⋮ Monadic second-order definable text languages ⋮ The monadic second-order logic of graphs. X: Linear orderings ⋮ Arity and alternation in second-order logic ⋮ The obstructions of a minor-closed set of graphs defined by a context-free grammar ⋮ Pushdown reachability with constant treewidth ⋮ On interval routing schemes and treewidth ⋮ Logical description of context-free graph languages ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Spanners of bounded degree graphs ⋮ Splitting a graph into disjoint induced paths or cycles. ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Automata for the verification of monadic second-order graph properties ⋮ The P3 infection time is W[1-hard parameterized by the treewidth] ⋮ Path-contractions, edge deletions and connectivity preservation ⋮ The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Upper bounds to the clique width of graphs ⋮ On the tree-width of even-hole-free graphs ⋮ Explicit linear kernels for packing problems ⋮ Counting linear extensions: parameterizations by treewidth ⋮ On the planar split thickness of graphs ⋮ Crossing number for graphs with bounded pathwidth ⋮ Canonical representations of partial 2- and 3-trees ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions ⋮ On distance-preserving elimination orderings in graphs: complexity and algorithms ⋮ On compatibility and incompatibility of collections of unrooted phylogenetic trees ⋮ Fly-automata for checking \(\mathrm{MSO}_2\) graph properties ⋮ Context-free hypergraph grammars have the same term-generating power as attribute grammars ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Algorithmic meta-theorems for restrictions of treewidth ⋮ Parameterized modal satisfiability ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Practical access to dynamic programming on tree decompositions ⋮ On the approximate compressibility of connected vertex cover ⋮ Complexity of path-forming games ⋮ Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width ⋮ Querying linguistic treebanks with monadic second-order logic in linear time ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ The complexity of frugal colouring ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Parameterized algorithms for conflict-free colorings of graphs ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Approximation in (Poly-) logarithmic space ⋮ Reducing graph transversals via edge contractions ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Algorithmic aspects of 2-secure domination in graphs ⋮ A unifying model for locally constrained spanning tree problems ⋮ Computing with graph rewriting systems with priorities ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Algorithmic aspects of Roman domination in graphs ⋮ Parameterized complexity of vertex colouring ⋮ A comparison of compatible, finite, and inductive graph properties ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs ⋮ Upper bounds on the size of obstructions and intertwines ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Nondeterministic operations on finite relational structures ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ On computing graph minor obstruction sets ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ The monadic second-order logic of graphs. VIII: Orientations ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Colouring non-even digraphs ⋮ A meta-theorem for distributed certification ⋮ Uniform and nonuniform recognizability. ⋮ Counting modulo quantifiers on finite structures ⋮ Reduction algorithms for graphs of small treewidth ⋮ On hyperedge replacement and BNLC graph grammars ⋮ FPT algorithms for generalized feedback vertex set problems ⋮ An FPT algorithm for matching cut and d-cut ⋮ Verifying graph programs with monadic second-order logic ⋮ On the impact of treewidth in the computational complexity of freezing dynamics ⋮ New limits of treewidth-based tractability in optimization

Cites Work

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