The nature and power of fixed-point logic with counting
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.
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}
}
EUVIMED