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

Deskribapen osoa

Xehetasun bibliografikoak

Argitaratua izan da:	Journal of the ACM 51, 2 (2004).
Egile nagusia:	Gottlob, Georg
Formatua:	Artikulua
Hizkuntza:	English
Gaiak:	Theory of computation. Analysis of algorithms and problem complexity. Tradeoffs among complexity measures. Mathematical logic and formal languages. Mathematical logic. Algorithms. Languages. Theory.