Descriptive complexity: a logician's approach to computation.

MaRDI QIDQ2769034zbMATH OpenFDO

Authors Neil Immerman

Publication date 4 February 2002

Published in Notices of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL http://www.ams.org/notices/199510/199510-toc.html

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited in

(18)

• A note on first-order projections and games.
• Expressive power of SQL.
• A descriptive complexity approach to the linear hierarchy.
• On the power of tree-walking automata.
• On the reducibility of sets inside NP to sets with low information content
• Adding for-loops to first-order logic
• Dichotomies for classes of homomorphism problems involving unary functions
• Boolean grammars
• Low-level dichotomy for quantified constraint satisfaction problems
• Complexity of local, global and universality properties in finite dynamical systems
• Descriptive complexity and revealed preference theory
• The first order theory of \(G(n, c/n)\)
• Categorical complexity
• A logical characterization of small 2NFAs
• On a question of Krajewski's
• Equilibrium semantics of languages of imperfect information
• Infinity problems and countability problems for -automata
• Reversal complexity revisited

This page was built for publication: Descriptive complexity: a logician's approach to computation.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2769034)