Algorithmic meta-theorems

MaRDI QIDQ3172385zbMATH OpenFDO

Authors Stephan Kreutzer

Publication date 5 October 2011

zbMATH Keywords

survey paper

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Graph minors (05C83) Analysis of algorithms and problem complexity (68Q25) General topics in the theory of algorithms (68W01)

Recommendations

• Logic, graphs, and algorithms
• Methods for algorithmic meta theorems
• Algorithmic meta theorems for sparse graph classes
• Algorithmic Meta-theorems
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes

Cited in

(32)

• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• Algorithmic Pirogov-Sinai theory
• On the weak 2-coloring number of planar graphs
• Colouring and covering nowhere dense graphs
• On ultralimits of sparse graph classes
• Large Induced Subgraphs via Triangulations and CMSO
• Logic, graphs, and algorithms
• Methods for algorithmic meta theorems
• Algorithmic Meta-theorems
• On the Parameterised Intractability of Monadic Second-Order Logic
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• Coloring and covering nowhere dense graphs
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Algorithmic meta theorems for sparse graph classes
• Recovering sparse graphs
• An algorithmic meta-theorem for graph modification to planarity and FOL
• The Complexity of Decomposing Modal and First-Order Theories
• Computations by fly-automata beyond monadic second-order logic
• On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Extended MSO model checking via small vertex integrity
• Model checking on interpretations of classes of bounded local cliquewidth
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Distributed model checking on graphs of bounded treedepth
• Complexity framework for forbidden subgraphs. I: The framework
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Compound logics for modification problems
• Advances in algorithmic meta theorems (invited paper)
• Structure-guided automated reasoning
• Learning aggregate queries defined by first-order logic with counting
• Courcelle's theorem for Lipschitz continuity

This page was built for publication: Algorithmic meta-theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3172385)