Practical algorithms for MSO model-checking on tree-decomposable graphs
From MaRDI portal
Logic in computer science (03B70) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- (Meta) Kernelization
- \texttt{Autowrite}: a tool for term rewrite systems and tree automata
- A combinatorial and logical approach to linear-time computability (extended abstract)
- A Linear Recognition Algorithm for Cographs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A mathematical introduction to logic.
- A partial k-arboretum of graphs with bounded treewidth
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Algorithmic meta theorems for circuit classes of constant and logarithmic depth
- Algorithmic meta-theorems
- Algorithmic meta-theorems for restrictions of treewidth
- Algorithmic uses of the Feferman-Vaught theorem
- Algorithms and models for railway optimization.
- All structured programs have small tree width and good register allocation
- Approximating clique-width and branch-width
- Automata for the verification of monadic second-order graph properties
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Back and forth between logic and games
- Bidimensionality and kernels
- Boolean-width of graphs
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Channel assignment on graphs of bounded treewidth
- Clique-width is NP-complete
- Combinatorial problems on series-parallel graphs
- Complexity of Finding Embeddings in a k-Tree
- Computations by fly-automata beyond monadic second-order logic
- Courcelle's theorem -- a game-theoretic approach
- Deciding first-order properties of locally tree-decomposable structures
- Decision Problems of Finite Automata Design and Related Arithmetics
- Directed Nowhere Dense Classes of Graphs
- Domino Treewidth
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Easy instances for model checking
- Easy problems for tree-decomposable graphs
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Evaluation of an MSO-Solver
- Exact algorithms for a loading problem with bounded clique width
- Fast Counting with Bounded Treewidth
- Finding Branch-Decompositions and Rank-Decompositions
- Finding good decompositions for dynamic programming on dense graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fly-automata, their properties and applications
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Graph minors. I. Excluding a forest
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XIII: The disjoint paths problem
- Graph operations characterizing rank-width
- Graph searching and a min-max theorem for tree-width
- Graph structure and monadic second-order logic. A language-theoretic approach
- Graph theory
- Graph-Theoretic Concepts in Computer Science
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 1805574 (Why is no real title available?)
- scientific article; zbMATH DE number 3819693 (Why is no real title available?)
- scientific article; zbMATH DE number 3917707 (Why is no real title available?)
- scientific article; zbMATH DE number 3974289 (Why is no real title available?)
- scientific article; zbMATH DE number 4060712 (Why is no real title available?)
- scientific article; zbMATH DE number 4095510 (Why is no real title available?)
- scientific article; zbMATH DE number 3761989 (Why is no real title available?)
- scientific article; zbMATH DE number 43826 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1257634 (Why is no real title available?)
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- scientific article; zbMATH DE number 475614 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2011862 (Why is no real title available?)
- scientific article; zbMATH DE number 2044940 (Why is no real title available?)
- scientific article; zbMATH DE number 1773084 (Why is no real title available?)
- scientific article; zbMATH DE number 1361465 (Why is no real title available?)
- scientific article; zbMATH DE number 1926662 (Why is no real title available?)
- scientific article; zbMATH DE number 4121438 (Why is no real title available?)
- scientific article; zbMATH DE number 2090086 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- scientific article; zbMATH DE number 1424025 (Why is no real title available?)
- scientific article; zbMATH DE number 969067 (Why is no real title available?)
- scientific article; zbMATH DE number 5585443 (Why is no real title available?)
- scientific article; zbMATH DE number 6783431 (Why is no real title available?)
- scientific article; zbMATH DE number 3266604 (Why is no real title available?)
- scientific article; zbMATH DE number 3399180 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
- Linear-time computability of combinatorial problems on series-parallel graphs
- Linear-time computation of optimal subgraphs of decomposable graphs
- Logic, graphs, and algorithms
- Lower bounds on the complexity of \(\mathrm{MSO}_1\) model-checking
- Mathematical logic.
- Methods for algorithmic meta theorems
- Model-checking by infinite fly-automata
- Modest theory of short chains. I
- Modified parameterized complexity theory
- Monadic Datalog and the expressive power of languages for web information extraction
- Monadic Datalog over finite structures of bounded treewidth
- Monadic second-order evaluations on tree-decomposable graphs
- On converting CNF to DNF
- On nowhere dense graphs
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On simple characterizations of k-trees
- On the clique-width of some perfect graph classes
- On the model-checking of monadic second-order formulas with edge set quantifications
- On the Parameterised Intractability of Monadic Second-Order Logic
- On the parameterized intractability of monadic second-order logic
- On the Relationship Between Clique-Width and Treewidth
- Optimization, approximation, and complexity classes
- Parametrized complexity theory.
- Polynomial-time recognition of clique-width 3 graphs
- Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
- Query evaluation via tree-decompositions
- Querying linguistic treebanks with monadic second-order logic in linear time
- Recontamination does not help to search a graph
- Regularity and locality in \(k\)-terminal graphs
- S-functions for graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Sparsity. Graphs, structures, and algorithms
- Special tree-width and the verification of monadic second-order graph properties
- Testing branch-width
- The Complexity of Enumeration and Reliability Problems
- The complexity of first-order and monadic second-order logic revisited
- The Complexity of Translating Logic to Finite Automata
- The DLV system for knowledge representation and reasoning
- The first order properties of products of algebraic systems
- The monadic second-order logic evaluation problem on finite colored trees: a database-theoretic approach
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The NP-completeness column: an ongoing guide
- The number of labeled k-dimensional trees
- The polynomial-time hierarchy
- The station location problem on two intersecting lines
- Tree acceptors and some of their applications
- Tree-depth, subgraph coloring and homomorphism bounds
- Treewidth computations. I: Upper bounds
- Treewidth computations. II. Lower bounds
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Upper bounds to the clique width of graphs
- Weak Second‐Order Arithmetic and Finite Automata
- When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
- Which problems have strongly exponential complexity?
Cited in
(18)- Computing the clique-width of cactus graphs
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
- Realizability and verification of MSC graphs
- Complexity of the multilevel critical node problem
- The complexity of restricted star colouring
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
- Easy problems for tree-decomposable graphs
- Extension complexity, MSO logic, and treewidth
- scientific article; zbMATH DE number 4081531 (Why is no real title available?)
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Courcelle's theorem -- a game-theoretic approach
- Transforming graph states using single-qubit operations
- Optimizing tree decompositions in MSO
- Computations by fly-automata beyond monadic second-order logic
- The firebreak problem
- Solving a family of multivariate optimization and decision problems on classes of bounded expansion
- Temporal reachability dominating sets: contagion in temporal graphs
- Enumeration of minimal hitting sets parameterized by treewidth
This page was built for publication: Practical algorithms for MSO model-checking on tree-decomposable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q473216)
