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...

Descrizione completa

Dettagli Bibliografici

Pubblicato in:	Journal of the ACM 51, 2 (2004).
Autore principale:	Gottlob, Georg
Natura:	Articolo
Lingua:	English
Soggetti:	Theory of computation. Analysis of algorithms and problem complexity. Tradeoffs among complexity measures. Mathematical logic and formal languages. Mathematical logic. Algorithms. Languages. Theory.