Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 73

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 80
CiE 2006 - Regular Talk: - Partially ordered connectives and ∑<sub>1</sub><sup>1</sup> on finite models
Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Partially ordered connectives and ∑11 on finite models

Author(s): Merlijn Sevenster and Tero Tulenheimo
Slot: Sat, 14:50-15:10, Faraday E (col. 4)

Abstract

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
2006-04-19 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net