Name
Abstract | ||
|---|---|---|
In this paper we take up the study of Henkin quantifiers with boolean variables [4], also known as partially ordered connectives [19]. We consider first-order formulae prefixed by partially ordered connectives, denoted D, on finite structures. D is characterized as a fragment of second-order existential logic Sigma(1)(1)heart, whose formulae do not allow existential variables as arguments of predicate variables. By means of a game theoretic argument, it is shown that Sigma(1)(1) heart harbors a strict hierarchy induced by the arity of predicate variables, and that it is not closed under complementation. It is further shown that allowing at most one existential variable to appear as an argument of a predicate variable, already yields a logic coinciding with full Sigma(1)(1). |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11780342_52 | LECTURE NOTES IN COMPUTER SCIENCE |
Keywords | DocType | Volume |
Henkin quantifiers,partially ordered connectives,NP vs. coNP,finite model theory | Conference | 3988 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.35 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Merlijn Sevenster | 1 | 98 | 13.33 |
| Tero Tulenheimo | 2 | 16 | 5.19 |