Practical algorithms for MSO model-checking on tree-decomposable graphs
type: Item
instance of: scholarly article
title: Practical algorithms for MSO model-checking on tree-decomposable graphs
zbMATH Open document ID: 1302.68184
author: Alexander Langer
author: Felix Reidl
author: Peter Rossmanith
author: Somnath Sikdar
published in: Computer Science Review
publication date: 2014-11-24T00:00:00Z
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 03B15
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 6372046
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: tree decompositions
zbMATH Keywords: Courcelle's theorem
describes a project that uses: Treewidthlib
describes a project that uses: Datalog
describes a project that uses: Autowrite
describes a project that uses: CPLEX
describes a project that uses: MONA
MaRDI profile type: Publication
full work available at URL: j.cosrev.2014.08.001
OpenAlex ID: W2158543468
cites work: Algorithms and Data Structures
cites work: Q4437514
cites work: The station location problem on two intersecting lines
cites work: Q5322945
cites work: Q4198056
cites work: The NP-completeness column: an ongoing guide
cites work: S-functions for graphs
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Q4393480
cites work: Parametrized complexity theory.
cites work: Q3577833
cites work: Q4734768
cites work: Q3822197
cites work: Q4385515
cites work: All structured programs have small tree width and good register allocation
cites work: Q4291429
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: Linear-time computability of combinatorial problems on series-parallel graphs
cites work: Combinatorial problems on series-parallel graphs
cites work: Q3740231
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
cites work: Linear-time computation of optimal subgraphs of decomposable graphs
cites work: Regularity and locality in \(k\)-terminal graphs
cites work: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
cites work: Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
cites work: Q3795218
cites work: Q3692864
cites work: A combinatorial and logical approach to linear-time computability (extended abstract)
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Easy problems for tree-decomposable graphs
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Query evaluation via tree-decompositions
cites work: Optimization, approximation, and complexity classes
cites work: (Meta) Kernelization
cites work: Bidimensionality and Geometric Graphs
cites work: Algorithmic meta theorems for circuit classes of constant and logarithmic depth
cites work: Q3086928
cites work: Q3172385
cites work: Q3118384
cites work: Q5710169
cites work: Monadic datalog over finite structures of bounded treewidth
cites work: Q4945215
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Decision Problems of Finite Automata Design and Related Arithmetics
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
cites work: Tree acceptors and some of their applications
cites work: Q4540967
cites work: The complexity of first-order and monadic second-order logic revisited

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q3077955

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Automata for the verification of monadic second-order graph properties

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Bounded treewidth as a key to tractability of knowledge representation and reasoning

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4699283

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q5365079

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Recontamination does not help to search a graph

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Graph searching and a min-max theorem for tree-width

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: The number of labeled k-dimensional trees

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On simple characterizations of k-trees

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Sparsity. Graphs, structures, and algorithms

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4707790

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Complexity of Finding Embeddings in a k-Tree

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Graph minors. XIII: The disjoint paths problem

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Treewidth computations. I: Upper bounds

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Treewidth computations. II. Lower bounds

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q3148848

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: A mathematical introduction to logic.

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4229041

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Mathematical logic.

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q3993126

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4255575

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: The polynomial-time hierarchy

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q5284545

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q3666827

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q5551141

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Deciding first-order properties of locally tree-decomposable structures

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On nowhere dense graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Deciding First-Order Properties of Nowhere Dense Graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: The Complexity of Enumeration and Reliability Problems

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: A uniform method for proving lower bounds on the computational complexity of logical theories

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Easy instances for model checking

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q5451198

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4273870

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: The first order properties of products of algebraic systems

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Modest theory of short chains. I

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Algorithmic uses of the Feferman-Vaught theorem

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q3637999

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Courcelle's theorem -- a game-theoretic approach

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q5666510

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q3172530

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: The Complexity of Translating Logic to Finite Automata

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Linear time solvable optimization problems on graphs of bounded clique-width

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Querying linguistic treebanks with monadic second-order logic in linear time

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Exact algorithms for a loading problem with bounded clique width

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Channel assignment on graphs of bounded treewidth

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On converting CNF to DNF

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4808760

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: \texttt{Autowrite}: a tool for term rewrite systems and tree automata

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Fly-Automata, Their Properties and Applications

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Computations by fly-automata beyond monadic second-order logic

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Model-Checking by Infinite Fly-Automata

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4864249

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: The DLV system for knowledge representation and reasoning

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Monadic datalog and the expressive power of languages for Web information extraction

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Fast Counting with Bounded Treewidth

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Evaluation of an MSO-Solver

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q3944542

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Handle-rewriting hypergraph grammars

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Upper bounds to the clique width of graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On the Relationship Between Clique-Width and Treewidth

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Graph-Theoretic Concepts in Computer Science

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Clique-Width is NP-Complete

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: A Linear Recognition Algorithm for Cographs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Polynomial-time recognition of clique-width \(\leq 3\) graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Q4448762

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Approximating clique-width and branch-width

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Graph minors. X: Obstructions to tree-decomposition

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Graph operations characterizing rank-width

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Finding Branch-Decompositions and Rank-Decompositions

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Testing branch-width

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Boolean-width of graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Finding Good Decompositions for Dynamic Programming on Dense Graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Domino Treewidth

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Graph minors. I. Excluding a forest

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On the model-checking of monadic second-order formulas with edge set quantifications

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Special tree-width and the verification of monadic second-order graph properties

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Algorithmic meta-theorems for restrictions of treewidth

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Tree-depth, subgraph coloring and homomorphism bounds

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: When Trees Grow Low: Shrubs and Fast MSO1

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On the Parameterised Intractability of Monadic Second-Order Logic

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: On the parameterized intractability of monadic second-order logic

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Directed Nowhere Dense Classes of Graphs

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Which problems have strongly exponential complexity?

Practical algorithms for MSO model-checking on tree-decomposable graphs (cites work)
cites work: Lower bounds on the complexity of \(\mathrm{MSO}_1\) model-checking

Practical algorithms for MSO model-checking on tree-decomposable graphs (DOI)
DOI: 10.1016/J.COSREV.2014.08.001