Enhancing fixed point logic with cardinality quantifiers
Copyright policy )Enhancing fixed point logic with cardinality quantifiers
Let \(Q_{\text{IFP}}\) be any quantifier such that \(FO(Q_{\text{IFP}}) \equiv \text{IFP}\). It has been shown by the second author [ibid. 7, 405-425 (1997; Zbl 0880.03012)] that there are quantifiers \(Q\) such that \(FO(Q_{\text{IFP}}, Q)<\text{IFP} (Q)\). In the present, clearly written paper the authors classify the simple cardinal quantifiers \(Q\) with this property.
- University of Freiburg Germany
- RERO - Library Network of Western Switzerland Switzerland
- Swansea University United Kingdom
- University of Helsinki Finland
descriptive complexity theory, Complexity of computation (including implicit computational complexity), finite model theory, cardinal quantifiers, Logic with extra quantifiers and operators, generalized quantifiers, fixed point logics, Complexity classes (hierarchies, relations among complexity classes, etc.), Model theory of finite structures
descriptive complexity theory, Complexity of computation (including implicit computational complexity), finite model theory, cardinal quantifiers, Logic with extra quantifiers and operators, generalized quantifiers, fixed point logics, Complexity classes (hierarchies, relations among complexity classes, etc.), Model theory of finite structures
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!