Computability in Europe 2006
Logical Approaches to Computational Barriers
|Author(s):||Merlijn Sevenster and Tero Tulenheimo|
|Slot:||Sat, 14:50-15:10, Faraday E (col. 4)|
In this paper we take up the study of Henkin quantifiers with boolean variables (Blass & Gurevich, 1986) also known as partially ordered connectives (Sandu & Vaananen, 1992). We consider first-order formulae prefixed by partially ordered connectives, denoted D, on finite structures. We characterize D as a fragment of second-order existential logic (\Sigma_1^1) whose formulae do not allow for existential variables being argument of predicate variables. We show that this fragments harbors a strict hierarchy induced by the arity of predicate variables and that it is not closed under complementation, by means of a game-theoretical argument. Admitting for at most one existential variable to appear as the argument of a predicate variable already yields a logic coinciding with full second-order existential logic, thus we show.
|websites: Arnold Beckmann||
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135