EUVIMEDEUVIMED entdecken
Crossref

The nature and power of fixed-point logic with counting

Anuj Dawar

ACM SIGLOG News · 2015

DOI: 10.1145/2728816.2728820 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGLOG News, 2015. Verfasst von Anuj Dawar. Die Arbeit wurde bisher 20-mal zitiert (Crossref) und nennt 38 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In 1982, Neil Immerman proposed an extension of fixed-point logic by means of counting quantifiers (which we denote FPC) as a logic that might express all polynomial-time properties of unordered graphs. It was eventually proved (by Cai, Fürer and Immerman) that there are polynomial-time graph properties that are not expressible in FPC. Nonetheless, FPC is a powerful and natural fragment of the complexity class PTime. In this article, I justify this claim by reviewing three recent positive results that demonstrate the expressive power and robustness of this logic.

Zitieren

APA

Dawar, A. (2015). The nature and power of fixed-point logic with counting. ACM SIGLOG News. https://doi.org/10.1145/2728816.2728820

Vancouver

Dawar A. The nature and power of fixed-point logic with counting. ACM SIGLOG News. 2015. doi:10.1145/2728816.2728820

BibTeX
@article{Dawar2015,
  author = {Dawar, Anuj},
  title = {The nature and power of fixed-point logic with counting},
  journal = {ACM SIGLOG News},
  year = {2015},
  doi = {10.1145/2728816.2728820}
}
Kostenlos starten →