Practical algorithms for MSO model-checking on tree-decomposable graphs
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Specification and verification (program logics, model checking, etc.) (68Q60) Logic in computer science (03B70)
Recommendations
Cites work
- 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?)
- (Meta) Kernelization
- A Linear Recognition Algorithm for Cographs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A combinatorial and logical approach to linear-time computability (extended abstract)
- 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
- 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 Parameterised Intractability of Monadic Second-Order Logic
- On the Relationship Between Clique-Width and Treewidth
- On the clique-width of some perfect graph classes
- On the model-checking of monadic second-order formulas with edge set quantifications
- On the parameterized intractability of monadic second-order logic
- Optimization, approximation, and complexity classes
- Parametrized complexity theory.
- Polynomial-time recognition of clique-width \(\leq 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 Translating Logic to Finite Automata
- The DLV system for knowledge representation and reasoning
- The NP-completeness column: an ongoing guide
- The complexity of first-order and monadic second-order logic revisited
- 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 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?
- \texttt{Autowrite}: a tool for term rewrite systems and tree automata
Cited in
(13)- Complexity of the multilevel critical node problem
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
- The complexity of restricted star colouring
- Courcelle's theorem -- a game-theoretic approach
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- The firebreak problem
- Computations by fly-automata beyond monadic second-order logic
- Realizability and verification of MSC graphs
- scientific article; zbMATH DE number 4081531 (Why is no real title available?)
- Transforming graph states using single-qubit operations
- Computing the clique-width of cactus graphs
- Extension complexity, MSO logic, and 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)
