Descriptive complexity and model checking

DOI10.1007/978-3-540-49382-2_1MaRDI QIDQ4247261zbMATH OpenFDO

Authors Neil Immerman

Publication date 7 December 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-49382-2_1

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

Introduction to the author's talk held at the conference. For the entire collection see [Zbl 0903.00078].

Cited in

(24)

• Hardness of equivalence checking for composed finite-state systems
• Voting by eliminating quantifiers
• An infinite hierarchy of temporal logics over branching time
• Annotation theories over finite graphs
• Knowledge representation analysis of graph mining
• On the space and circuit complexity of parameterized problems: classes and completeness
• Generic incremental algorithms for local search
• Epsilon-logic is more expressive than first-order logic over finite structures
• Number of variables is equivalent to space
• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• A logical characterization of small 2NFAs
• The probability nesting game
• Formal descriptions of code properties: decidability, complexity, implementation
• An extension of the Ehrenfeucht-Fraïssé game for first order logics augmented with Lindström quantifiers
• Descriptive complexity of finite abelian groups
• Parameterized Complexity Classes under Logical Reductions
• \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
• COMPLEXITY, INFORMATION, ENERGY
• Approximate databases: a support tool for approximate reasoning
• 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02
• Book review of: E. Grädel, P. Kolaitis, L. Libkin, M. Marx, I. Spencer, M. Vardi, Y. Venema, S. Weinstein, Finite model theory and its applications
• Characterizing polynomial Ramsey quantifiers
• Capturing the polynomial hierarchy by second-order revised Krom logic

This page was built for publication: Descriptive complexity and model checking

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