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

詳細記述

書誌詳細

出版年:	Journal of the ACM 51, 2 (2004).
第一著者:	Gottlob, Georg
フォーマット:	論文
言語:	English
主題:	Theory of computation. Analysis of algorithms and problem complexity. Tradeoffs among complexity measures. Mathematical logic and formal languages. Mathematical logic. Algorithms. Languages. Theory.