Algorithmic uses of the Feferman-Vaught theorem

DOI10.1016/J.APAL.2003.11.002zbMath1099.03009OpenAlexW2085467680MaRDI QIDQ598280

Johann A. Makowsky

Publication date: 6 August 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2003.11.002

zbMATH Keywords

Clique widthGraph algorithmsGraph polynomialsMonadic second-order logicTree width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Interpolation, preservation, definability (03C40)

Related Items (67)

Trees, grids, and MSO decidability: from graphs to matroids ⋮ On countable chains having decidable monadic theory ⋮ Why Horn formulas matter in computer science: initial structures and generic examples ⋮ Simple monadic theories and partition width ⋮ Parameterized model checking of rendezvous systems ⋮ Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries ⋮ Logical properties of random graphs from small addable classes ⋮ A Most General Edge Elimination Polynomial ⋮ Evaluations of Graph Polynomials ⋮ Complexity of Ising Polynomials ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Bisimulation invariant monadic-second order logic in the finite ⋮ Logics of Finite Hankel Rank ⋮ Complexity of the Bollobás-Riordan Polynomial ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Feferman-vaught decompositions for prefix classes of first order logic ⋮ Model-checking hierarchical structures ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Continuous time temporal logic with counting ⋮ Unnamed Item ⋮ First-order separation over countable ordinals ⋮ Fixpoint logics over hierarchical structures ⋮ On algebraic array theories ⋮ Singularities in Negami's splitting formula for the Tutte polynomial ⋮ Unnamed Item ⋮ Tarski’s Influence on Computer Science ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ Regular languages of nested words: fixed points, automata, and synchronization ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ Bisimulation Invariant Monadic-Second Order Logic in the Finite ⋮ A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Circle graphs and monadic second-order logic ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Effective optimization with weighted automata on decomposable trees ⋮ Game-based notions of locality over finite models ⋮ A Practical Approach to Courcelle's Theorem ⋮ The independence polynomial of rooted products of graphs ⋮ Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width ⋮ On the colored Tutte polynomial of a graph of bounded treewidth ⋮ Recognizability, hypergraph operations, and logical types ⋮ A logician's view of graph polynomials ⋮ Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions ⋮ Connection Matrices for MSOL-Definable Structural Invariants ⋮ Unnamed Item ⋮ Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees ⋮ Compositional Failure Detection in Structured Transition Systems ⋮ Linear Recurrence Relations for Graph Polynomials ⋮ Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications ⋮ The Complexity of Decomposing Modal and First-Order Theories ⋮ Decidable Expansions of Labelled Linear Orderings ⋮ On the location of roots of graph polynomials ⋮ Recurrence relations for graph polynomials on bi-iterative families of graphs ⋮ From Choosing Elements to Choosing Concepts: The Evolution of Feferman’s Work in Model Theory ⋮ Where First-Order and Monadic Second-Order Logic Coincide ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ Unnamed Item ⋮ Semantic Equivalence of Graph Polynomials Definable in Second Order Logic ⋮ Model Checking FO(R) over One-Counter Processes and beyond ⋮ Graph operations characterizing rank-width ⋮ From Hilbert's program to a logic tool box ⋮ COMPOSITIONALITY AND REACHABILITY WITH CONDITIONS ON PATH LENGTHS ⋮ An extension of the bivariate chromatic polynomial ⋮ The recognizability of sets of graphs is a robust property ⋮ A logic-based approach to incremental reasoning on multi-agent systems

Cites Work

• The complexity of computing the permanent
• Hyperedge replacement: grammars and languages
• Monadic second-order evaluations on tree-decomposable graphs
• Tutte polynomials computable in polynomial time
• The structure of the models of decidable monadic theories of graphs
• A uniform method for proving lower bounds on the computational complexity of logical theories
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• Matching theory
• Power properties of NLC graph grammars with a polynomial membership problem
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Model theory.
• On a general class of graph polynomials
• S-functions for graphs
• The monadic theory of order
• The polynomial-time hierarchy
• The computational complexity of logical theories
• Clique polynomials and independent set polynomials of graphs
• Monadic second-order definable graph transductions: a survey
• Regularity and locality in \(k\)-terminal graphs
• \(k\)-NLC graphs and polynomial algorithms
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Problems in algebraic combinatorics
• A hierarchy of eNCE families of graph languages
• Farrell polynomials on graphs of bounded tree width
• On the algebraic complexity of some families of coloured Tutte polynomials
• Completeness and reduction in algebraic complexity theory
• New results for the Martin polynomial
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• The parametrized complexity of knot polynomials
• Arity and alternation in second-order logic
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Dependence polynomials
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Undecidable theories
• Some Graph Theoretical Operations and Decidability
• The Specker-Blatter Theorem Revisited
• Fusion in relational structures and the verification of monadic second-order properties
• Universal relational systems
• On isomorphism types of groups and other algebraic systems
• The first order properties of products of algebraic systems
• An application of games to the completeness problem for formalized theories
• Weak Second‐Order Arithmetic and Finite Automata
• Le Polynôme De Martin D'un Graphe Eulerien
• On Some Variants of the Bandwidth Minimization Problem
• Easy problems for tree-decomposable graphs
• A lattice of chapters of mathematics (interpretations between theorems [theories)]
• Incremental model checking for decomposable structures
• Complexity of Finding Embeddings in a k-Tree
• Tutte Polynomials and Link Polynomials
• Reduced direct products
• Decision Problems of Finite Automata Design and Related Arithmetics
• The Complexity of Enumeration and Reliability Problems
• The computational complexity of matroid properties
• Algorithmic versus axiomatic definitions of matroids
• Modest theory of short chains. I
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Two notes on abstract model theory. I. Properties invariant on the range of definable relations between structures
• Some observations on Uniform Reduction for properties invariant on the range of definable relations
• Application of model theoretic games to discrete linear orders and finite automata
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• A Tutte Polynomial for Coloured Graphs
• Graph Classes: A Survey
• Definability in Rationals with Real Order in the Background
• Handbook of Graph Grammars and Computing by Graph Transformation
• Dependency preserving refinements and the fundamental problem of database design
• Definability and undefinability with real order at the background
• COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS
• On the Very Weak 0–1 Law for Random Graphs with Orders
• Handbook of Graph Grammars and Computing by Graph Transformation
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the elementary theory of linear order
• Homogeneous Universal Relational Systems.
• On Extensions of Elementary Logic
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Infinitary analogs of theorems from first order model theory
• Persistent and invariant formulas relative to theories of higher order
• On direct products of theories
• A Contribution to the Theory of Chromatic Polynomials
• Elementary properties of Abelian groups
• Beitrag zur Aerodynamik eines schwingenden Gitters II (Unterschallströmung)
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Efficient recognition algorithms for boundary and linear eNCE graph languages
• 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
• 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
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithmic uses of the Feferman-Vaught theorem