Existential second-order logic over graphs Charting the tractability frontier.

Fagin's theorem, the first important result of descriptive complexity, asserts that a property of graphs is in NP if and only if it is definable by an existential second-order formula. In this article, we study the complexity of evaluating existential second-order formulas that belong to prefix...

Full description

Bibliographic Details

Published in:	Journal of the ACM 51, 2 (2004).
Main Author:	Gottlob, Georg
Format:	Article
Language:	English
Subjects:	Theory of computation. Analysis of algorithms and problem complexity. Tradeoffs among complexity measures. Mathematical logic and formal languages. Mathematical logic. Algorithms. Languages. Theory.