Algorithmic uses of the Feferman-Vaught theorem

DOI10.1016/j.apal.2003.11.002zbMath1099.03009MaRDI 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 width; Graph algorithms; Graph polynomials; Monadic second-order logic; Tree width

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B25: Decidability of theories and sets of sentences

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

03C40: Interpolation, preservation, definability

Related Items

A Most General Edge Elimination Polynomial, Evaluations of Graph Polynomials, Linear Recurrence Relations for Graph Polynomials, Trees, grids, and MSO decidability: from graphs to matroids, Vertex-minors, monadic second-order logic, and a conjecture by Seese, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Circle graphs and monadic second-order logic, From a zoo to a zoology: Towards a general theory of graph polynomials, Why Horn formulas matter in computer science: initial structures and generic examples, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Counting truth assignments of formulas of bounded tree-width or clique-width, Game-based notions of locality over finite models, On the colored Tutte polynomial of a graph of bounded treewidth, Recognizability, hypergraph operations, and logical types, The recognizability of sets of graphs is a robust property, Complexity of the Bollobás-Riordan Polynomial, Connection Matrices for MSOL-Definable Structural Invariants, Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees, Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications

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