Algorithmic uses of the Feferman-Vaught theorem
From MaRDI portal
Decidability of theories and sets of sentences (03B25) Interpolation, preservation, definability (03C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Recommendations
Cites work
- \(k\)-NLC graphs and polynomial algorithms
- A comparison of boundary graph grammars and context-free hypergraph grammars
- A Contribution to the Theory of Chromatic Polynomials
- A hierarchy of eNCE families of graph languages
- A lattice of chapters of mathematics (interpretations between theorems [theories])
- A Tutte Polynomial for Coloured Graphs
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Algorithmic versus axiomatic definitions of matroids
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- An application of games to the completeness problem for formalized theories
- Application of model theoretic games to discrete linear orders and finite automata
- Arity and alternation in second-order logic
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Beitrag zur Aerodynamik eines schwingenden Gitters II (Unterschallströmung)
- Clique polynomials and independent set polynomials of graphs
- Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Completeness and reduction in algebraic complexity theory
- Complexity of Finding Embeddings in a k-Tree
- COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS
- Context-free graph languages of bounded degree are generated by apex graph grammars
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Decision Problems of Finite Automata Design and Related Arithmetics
- Definability and undefinability with real order at the background
- Definability in Rationals with Real Order in the Background
- Dependence polynomials
- Dependency preserving refinements and the fundamental problem of database design
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Easy problems for tree-decomposable graphs
- Efficient recognition algorithms for boundary and linear eNCE graph languages
- Elementary properties of Abelian groups
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- Farrell polynomials on graphs of bounded tree width
- Fusion in relational structures and the verification of monadic second-order properties
- Graph Classes: A Survey
- Graph minors. I. Excluding a forest
- Graph minors. V. Excluding a planar graph
- Handbook of Graph Grammars and Computing by Graph Transformation
- Handbook of Graph Grammars and Computing by Graph Transformation
- Handle-rewriting hypergraph grammars
- Homogeneous Universal Relational Systems.
- scientific article; zbMATH DE number 1688350 (Why is no real title available?)
- scientific article; zbMATH DE number 3836093 (Why is no real title available?)
- scientific article; zbMATH DE number 437298 (Why is no real title available?)
- scientific article; zbMATH DE number 3885330 (Why is no real title available?)
- scientific article; zbMATH DE number 3885853 (Why is no real title available?)
- scientific article; zbMATH DE number 3127542 (Why is no real title available?)
- scientific article; zbMATH DE number 3171141 (Why is no real title available?)
- scientific article; zbMATH DE number 3880787 (Why is no real title available?)
- scientific article; zbMATH DE number 3914328 (Why is no real title available?)
- scientific article; zbMATH DE number 3941493 (Why is no real title available?)
- scientific article; zbMATH DE number 3941494 (Why is no real title available?)
- scientific article; zbMATH DE number 4053039 (Why is no real title available?)
- scientific article; zbMATH DE number 3720895 (Why is no real title available?)
- scientific article; zbMATH DE number 3744549 (Why is no real title available?)
- scientific article; zbMATH DE number 3767656 (Why is no real title available?)
- scientific article; zbMATH DE number 53151 (Why is no real title available?)
- scientific article; zbMATH DE number 67324 (Why is no real title available?)
- scientific article; zbMATH DE number 3472038 (Why is no real title available?)
- scientific article; zbMATH DE number 3485778 (Why is no real title available?)
- scientific article; zbMATH DE number 3550662 (Why is no real title available?)
- scientific article; zbMATH DE number 3563060 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1254648 (Why is no real title available?)
- scientific article; zbMATH DE number 1262783 (Why is no real title available?)
- scientific article; zbMATH DE number 618821 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 1142314 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 2044924 (Why is no real title available?)
- scientific article; zbMATH DE number 2080462 (Why is no real title available?)
- scientific article; zbMATH DE number 1512682 (Why is no real title available?)
- scientific article; zbMATH DE number 1361465 (Why is no real title available?)
- scientific article; zbMATH DE number 803291 (Why is no real title available?)
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- scientific article; zbMATH DE number 1437942 (Why is no real title available?)
- scientific article; zbMATH DE number 3204616 (Why is no real title available?)
- scientific article; zbMATH DE number 3222645 (Why is no real title available?)
- scientific article; zbMATH DE number 3259043 (Why is no real title available?)
- scientific article; zbMATH DE number 3273148 (Why is no real title available?)
- scientific article; zbMATH DE number 3286895 (Why is no real title available?)
- scientific article; zbMATH DE number 3290311 (Why is no real title available?)
- scientific article; zbMATH DE number 3304995 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3316928 (Why is no real title available?)
- scientific article; zbMATH DE number 3328129 (Why is no real title available?)
- scientific article; zbMATH DE number 3085803 (Why is no real title available?)
- Hyperedge replacement: grammars and languages
- Incremental model checking for decomposable structures
- Infinitary analogs of theorems from first order model theory
- Le Polynôme De Martin D'un Graphe Eulerien
- Linear time solvable optimization problems on graphs of bounded clique-width
- Matching theory
- Model theory.
- Modest theory of short chains. I
- Monadic second-order definable graph transductions: a survey
- Monadic second-order evaluations on tree-decomposable graphs
- New results for the Martin polynomial
- On a general class of graph polynomials
- On direct products of theories
- On Extensions of Elementary Logic
- On isomorphism types of groups and other algebraic systems
- On Some Variants of the Bandwidth Minimization Problem
- On the algebraic complexity of some families of coloured Tutte polynomials
- On the clique-width of graph with few \(P_{4}\)'s
- On the clique-width of some perfect graph classes
- On the elementary theory of linear order
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- On the interplay between graphs and matroids
- On the Very Weak 0–1 Law for Random Graphs with Orders
- Persistent and invariant formulas relative to theories of higher order
- Power properties of NLC graph grammars with a polynomial membership problem
- Problems in algebraic combinatorics
- Reduced direct products
- Regularity and locality in \(k\)-terminal graphs
- S-functions for graphs
- Some Graph Theoretical Operations and Decidability
- Some observations on Uniform Reduction for properties invariant on the range of definable relations
- The complexity of computing the permanent
- The Complexity of Enumeration and Reliability Problems
- The computational complexity of logical theories
- The computational complexity of matroid properties
- The first order properties of products of algebraic systems
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The monadic theory of order
- The parametrized complexity of knot polynomials
- The Penrose polynomial of graphs and matroids
- The polynomial-time hierarchy
- The Specker-Blatter theorem revisited
- The structure of the models of decidable monadic theories of graphs
- Tutte Polynomials and Link Polynomials
- Tutte polynomials computable in polynomial time
- Two notes on abstract model theory. I. Properties invariant on the range of definable relations between structures
- Undecidable theories
- Universal relational systems
- Upper bounds to the clique width of graphs
- Weak Second‐Order Arithmetic and Finite Automata
Cited in
(88)- From a zoo to a zoology: Towards a general theory of graph polynomials
- Graph operations characterizing rank-width
- From Hilbert's program to a logic tool box
- An extension of the bivariate chromatic polynomial
- Why Horn formulas matter in computer science: initial structures and generic examples
- Parameterized model checking of rendezvous systems
- Singularities in Negami's splitting formula for the Tutte polynomial
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- A logic-based approach to incremental reasoning on multi-agent systems
- Bisimulation invariant monadic-second order logic in the finite
- A logician's view of graph polynomials
- Fixpoint logics over hierarchical structures
- 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
- Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries
- Semantic equivalence of graph polynomials definable in second order logic
- On countable chains having decidable monadic theory
- Complexity of Ising polynomials
- Logics of finite Hankel rank
- Simple monadic theories and partition width
- Complexity of the Bollobás-Riordan Polynomial
- An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet
- 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
- Model Checking FO(R) over One-Counter Processes and beyond
- COMPOSITIONALITY AND REACHABILITY WITH CONDITIONS ON PATH LENGTHS
- Courcelle's theorem -- a game-theoretic approach
- Model-checking hierarchical structures
- Continuous time temporal logic with counting
- Tarski's influence on computer science
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Fifty years of the spectrum problem: survey and new results
- Bisimulation Invariant Monadic-Second Order Logic in the Finite
- Gaifman normal forms for counting extensions of first-order logic
- A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
- Counting problems in parameterized complexity
- Enumerating answers to first-order queries over databases of low degree
- A Practical Approach to Courcelle's Theorem
- Compositional failure detection in structured transition systems
- From choosing elements to choosing concepts: the evolution of Feferman's work in model theory
- Logical properties of random graphs from small addable classes
- Where first-order and monadic second-order logic coincide
- A Most General Edge Elimination Polynomial
- Evaluations of Graph Polynomials
- A strategy for dynamic programs: start over and muddle through
- Effective optimization with weighted automata on decomposable trees
- Composition theorem for generalized sum
- Linear Recurrence Relations for Graph Polynomials
- First-Order Model-Checking in Random Graphs and Complex Networks
- The Complexity of Decomposing Modal and First-Order Theories
- Feferman-vaught decompositions for prefix classes of first order logic
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- First-order separation over countable ordinals
- On algebraic array theories
- The enumeration of vertex induced subgraphs with respect to the number of components
- Regular languages of nested words: fixed points, automata, and synchronization
- A monadic second-order version of Tarski's geometry of solids
- How I got to like graph polynomials
- Axiomatizing origami planes
- Preservation theorems for Tarski's relation algebra
- Extensions and limits of the Specker-Blatter theorem
- When locality meets preservation
- Preservation theorems through the Lens of topology
- Extension preservation in the finite and prefix classes of first-order logic
- Extensions and limits of the Specker-Blatter theorem
- Derivatives on graphs for the positive calculus of relations with transitive closure
- A categorical account of composition methods in logic
- Meta-theorems for graph polynomials
- Maintaining \(\mathrm{CMSO}_2\) properties on dynamic structures with bounded feedback vertex number
- On first-order transductions of classes of graphs
- Expressiveness results for an inductive logic of separated relations
- My writing
- Automatic structures and the problem of natural well-orderings
- Graph polynomials: some questions on the edge
- The theory of concatenation over finite models
- Learning aggregate queries defined by first-order logic with counting
- On the location of roots of graph polynomials
- Recurrence relations for graph polynomials on bi-iterative families of graphs
- 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
- The independence polynomial of rooted products of graphs
- Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
This page was built for publication: Algorithmic uses of the Feferman-Vaught theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598280)
