Algorithmic uses of the Feferman-Vaught theorem

DOI10.1016/j.apal.2003.11.002zbMath1099.03009OpenAlexW2085467680MaRDI QIDQ598280

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 width Graph algorithms Graph polynomials Monadic second-order logic Tree 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

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