The complexity of first-order and monadic second-order logic revisited

DOI10.1016/j.apal.2004.01.007zbMath1062.03032OpenAlexW2066585576MaRDI QIDQ1886318

Publication date: 18 November 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.01.007

zbMATH Keywords

first-order logic monadic second-order logic parameterized complexity

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13)

Related Items

To drive or not to drive: a logical and computational analysis of European transport regulations, A new approach on locally checkable problems, Enumeration for FO Queries over Nowhere Dense Graphs, Graph Minors and Parameterized Algorithm Design, Bounded fixed-parameter tractability and reducibility, Fly-automata for checking monadic second-order properties of graphs of bounded tree-width, A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata, Inductive computations on graphs defined by clique-width expressions, Clique-perfectness and balancedness of some graph classes, The tree-width of C, Automata for XML -- a survey, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees, Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs, Grouped domination parameterized by vertex cover, twin cover, and beyond, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width, Courcelle's theorem -- a game-theoretic approach, Grouped domination parameterized by vertex cover, twin cover, and beyond, On low tree-depth decompositions, Feferman-vaught decompositions for prefix classes of first order logic, Model-checking hierarchical structures, On the model-checking of monadic second-order formulas with edge set quantifications, An optimal construction of Hanf sentences, Unnamed Item, Extended MSO model checking via small vertex integrity, Automata for the verification of monadic second-order graph properties, Parameterized Complexity of Safe Set, Generalizing input-driven languages: theoretical and practical benefits, Unnamed Item, Unnamed Item, Operator precedence temporal logic and model checking, Confronting intractability via parameters, Practical algorithms for MSO model-checking on tree-decomposable graphs, First-Order Model-Checking in Random Graphs and Complex Networks, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, A gentle introduction to applications of algorithmic metatheorems for space and circuit classes, Practical Access to Dynamic Programming on Tree Decompositions, Counting truth assignments of formulas of bounded tree-width or clique-width, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Fly-automata for checking \(\mathrm{MSO}_2\) graph properties, Lower Bounds for Kernelizations and Other Preprocessing Procedures, Algorithmic meta-theorems for restrictions of treewidth, Parameterized modal satisfiability, Comparing the succinctness of monadic query languages over finite trees, A Practical Approach to Courcelle's Theorem, Lower bounds for kernelizations and other preprocessing procedures, Linear delay enumeration and monadic second-order logic, Practical access to dynamic programming on tree decompositions, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Unnamed Item, Bounded treewidth as a key to tractability of knowledge representation and reasoning, Unnamed Item, Unnamed Item, The parameterized complexity of \(k\)-edge induced subgraphs, Linear Recurrence Relations for Graph Polynomials, Computations by fly-automata beyond monadic second-order logic, Unnamed Item, Unnamed Item, Unnamed Item, On the parameterized complexity of graph modification to first-order logic properties, On structural parameterizations of firefighting, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, Convex dominating sets in maximal outerplanar graphs, On problems without polynomial kernels, The recognizability of sets of graphs is a robust property, Unnamed Item, A logic-based approach to incremental reasoning on multi-agent systems, Structural tractability of enumerating CSP solutions

Cites Work