Record link: 
http://hdl.handle.net/20.500.12708/55407
-
Title: 
A Dichotomy Result for Ramsey Quantifiers
-
Citation: 
de Haan, R., & Szymanik, J. (2015). A Dichotomy Result for Ramsey Quantifiers. In V. de Paiva, R. J. G. B. de Queiroz, L. Moss, D. Leivant, & A. Grisi de Oliveira (Eds.), Logic, Language, Information, and Computation (pp. 69–80). Springer. https://doi.org/10.1007/978-3-662-47709-0_6
-
Publisher DOI: 
10.1007/978-3-662-47709-0_6
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
de Haan, Ronald 
Szymanik, Jakub 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Logic, Language, Information, and Computation 
-
ISBN: 
978-3-662-47708-3
-
DOI of the book: 
10.1007/978-3-662-47709-0
-
Date (published): 
2015
-
Event name: 
WoLLIC 2015 
-
Event date: 
20-Jul-2015 - 23-Jul-2015
-
Event place: 
Bloomington, USA, Non-EU
-
Number of Pages: 
12
-
Publisher: 
Springer, Berlin, Heidelberg
-
Peer reviewed: 
Yes
-
Keywords: 
dichotomy result; ramsey quantifiers
-
Abstract: 
Ramsey quantifiers are a natural object of study not only for logic and computer science, but also for formal semantics of natural language. Restricting attention to finite models leads to the natural question whether all Ramsey quantifiers are either polynomial-time computable or NP-hard, and whether we can give a natural characterization of the polynomial-time computable quantifiers. In this paper, we first show that there exist intermediate Ramsey quantifiers and then we prove a dichotomy result for a large and natural class of Ramsey quantifiers, based on a reasonable and widely-believed complexity assumption. We show that the polynomial-time computable quantifiers in this class are exactly the constant-log-bounded Ramsey quantifiers.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Informatik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

240
checked on Nov 23, 2023

Google ScholarTM

Check