A Practical Approach to Courcelle's Theorem

DOI10.1016/j.entcs.2009.08.028zbMath1291.03077OpenAlexW2042861896MaRDI QIDQ5170276

Alexander Langer, Joachim Kneis

Publication date: 23 July 2014

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2009.08.028

zbMATH Keywords

monadic second-order logictreewidthmodel-checkingparameterized algorithmsexact algorithmsCourcelle's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graph Minors and Parameterized Algorithm Design, Parameterized analysis and crossing minimization problems, A Note on the Minimum H-Subgraph Edge Deletion, Lifted inference with tree axioms, Confronting intractability via parameters, Tree \(t\)-spanners in outerplanar graphs via supply demand partition, Default logic and bounded treewidth, Structural parameterizations of Tracking Paths problem

Uses Software

• MONA

Cites Work

• Algorithmic uses of the Feferman-Vaught theorem
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. I. Excluding a forest
• The complexity of first-order and monadic second-order logic revisited
• Computing crossing numbers in quadratic time
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• 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
• Easy problems for tree-decomposable graphs
• Query evaluation via tree-decompositions
• Graph minors. II. Algorithmic aspects of tree-width
• Decision Problems of Finite Automata Design and Related Arithmetics
• Application of model theoretic games to discrete linear orders and finite automata
• Generalized finite automata theory with an application to a decision problem of second-order logic
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item