Descriptive complexity
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
This book takes the approach to understand computation and computational complexity from the point of view of logic. It starts with the necessary background from logic, arithmetical definability, first-order queries and complexity theory. It is demonstrated how the logical machinery can be applied to ``capture complexity classes, i.e. to characterize classes like P, NP and PSPACE in a totally machine-independent way, just via the set of possible finite models that some suitable formula can have. The logical formulas are further enriched by several operators, like induction, least fixed point operator, transitive closure and other concepts. Since descriptive complexity is inherently parallel in nature, it is particularly suitable to capture parallel complexity classes, like NC, AC, and others. To determine the precise range of expressibility of certain logics, so-called Ehrenfeucht-Fraïssé-games are a useful concept that is considered. Fagin's theorem states that NP is exactly the class of sets being expressible by existentially quantified second-order formulas. This result can be extended to the polynomial-time hierarchy. Using this descriptional complexity approach, the author shows the closure under complement of the nondeterministic space-complexity classes. The last chapters deal with more specialized topics, like first-order projections, generalized quantifiers, uniformity issues, pebble games, and ``almost all results. A section on lower bounds introduces Hastad's famous switching lemma. Finally, applications and future directions are addressed, like database theory, dynamic complexity, model checking, and temporal logic.
- Universal algebra and hardness results for constraint satisfaction problems
- Affine systems of equations and counting infinitary logic
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Partially ordered connectives and monadic monotone strict NP
- On the power of deep pushdown stacks
- Descriptive characterizations of computational complexity
- The dynamic complexity of transitive closure is in DynTC\(^{0}\).
- A descriptive complexity approach to the linear hierarchy.
- Incremental recomputation in local languages.
- On the complexity of single-rule datalog queries.
- A second-order system for polytime reasoning based on Grädel's theorem.
- On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
- Existential monadic second order logic on random rooted trees
- Axiomatisability and hardness for universal Horn classes of hypergraphs
- Counter machines and distributed automata -- a story about exchanging space and time
- Second-order propositional modal logic: expressiveness and completeness results
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
- Algorithmic meta-theorems for restrictions of treewidth
- Functions computable in polynomial space
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Approximate pattern matching and transitive closure logics.
- Describing parameterized complexity classes
- Closure properties of locally finite \(\omega\)-languages
- Arithmetical definability and computational complexity
- A trichotomy for regular simple path queries on graphs
- IF modal logic and classical negation
- On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra
- A logic-based approach to incremental reasoning on multi-agent systems
- Using model theory to find decidable and tractable description logics with concrete domains
- The fine-grained complexity of multi-dimensional ordering properties
- Bounded game-theoretic semantics for modal mu-calculus
- Local higher-order fixpoint iteration
- Computation on structures. Behavioural theory, logic, complexity
- Equivalence classes and conditional hardness in massively parallel computations
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- On the expressive power of TeamLTL and first-order team logic over hyperproperties
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Emptiness problems for distributed automata
- Descriptive complexity of \#P functions: a new perspective
- Work-sensitive dynamic complexity of formal languages
- First-order rewritability of ontology-mediated queries in linear temporal logic
- Two first-order logics of permutations
- Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
- Descriptive complexity and revealed preference theory
- Two-sided context specifications in formal grammars
- On symmetric circuits and fixed-point logics
- Succinct definitions in the first order theory of graphs
- Computing queries with higher-order logics
- Arity and alternation: a proper hierarchy in higher order logics
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Maintenance goals of agents in a dynamic environment: formulation and policy construction
- Computational complexities of axiomatic extensions of monoidal t-norm based logic
- Tight lower and upper bounds for the complexity of canonical colour refinement
- Contribution of Warsaw logicians to computational logic
- Parallelizing time with polynomial circuits
- Polynomial hierarchy graph properties in hybrid logic
- A characterization of definability of second-order generalized quantifiers with applications to non-definability
- Out of order quantifier elimination for standard quantified linear programs
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Implicit complexity over an arbitrary structure: Quantifier alternations
- Subtractive reductions and complete problems for counting complexity classes
- The first order definability of graphs with separators via the Ehrenfeucht game
- A reducibility for the dot-depth hierarchy
- \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
- The many faces of a translation
- Program verification with interacting analysis plugins
- Complexity of model checking for reaction systems
- Descriptive complexity of deterministic polylogarithmic time and space
- Capturing relativized complexity classes with Lindström quantifiers
- On the unusual effectiveness of logic in computer science
- Computation by interaction for space-bounded functional programming
- Division in logspace-uniform NC
- Experimental descriptive complexity
- Multiple usage of random bits in finite automata
- Structure and specification as sources of complexity
- Computational Complexity Via Finite Types
- Capturing MSO with one quantifier
- Existential second-order logic over graphs: a complete complexity-theoretic classification
- A logical approach to locality in pictures languages
- On the variable hierarchy of first-order spectra
- The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
- On the first-order complexity of induced subgraph isomorphism
- Combining Model Checking and Deduction
- The mu-calculus and Model Checking
- On FO 2 Quantifier Alternation over Words
- Monadic \(\Sigma^{1}_{1}\) and modal logic with quantified binary relations
- Squeezing Feasibility
- The ultra-weak Ash conjecture and some particular cases
- Reachability is in DynFO
- On the Descriptive Complexity of Linear Algebra
- Pure Pointer Programs with Iteration
- The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
- Languages that Capture Complexity Classes
- scientific article; zbMATH DE number 4106276 (Why is no real title available?)
- scientific article; zbMATH DE number 17544 (Why is no real title available?)
- Model-checking hierarchical structures
This page was built for publication: Descriptive complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4227581)
