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

Volledige beschrijving

Bibliografische gegevens

Gepubliceerd in:	Journal of the ACM 51, 2 (2004).
Hoofdauteur:	Gottlob, Georg
Formaat:	Artikel
Taal:	Engels
Onderwerpen:	Theory of computation. Analysis of algorithms and problem complexity. Tradeoffs among complexity measures. Mathematical logic and formal languages. Mathematical logic. Algorithms. Languages. Theory.