<div class="csl-bib-body">
<div class="csl-entry">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.), <i>Logic, Language, Information, and Computation</i> (pp. 69–80). Springer. https://doi.org/10.1007/978-3-662-47709-0_6</div>
</div>
-
dc.identifier.isbn
9783662477083
-
dc.identifier.isbn
9783662477090
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/55407
-
dc.description.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
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.subject
dichotomy result
-
dc.subject
ramsey quantifiers
-
dc.title
A Dichotomy Result for Ramsey Quantifiers
-
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
Logic, Language, Information, and Computation
-
dc.relation.isbn
978-3-662-47708-3
-
dc.relation.doi
10.1007/978-3-662-47709-0
-
dc.relation.issn
0302-9743
-
dc.description.startpage
69
-
dc.description.endpage
80
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Logic, Language, Information, and Computation
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Berlin, Heidelberg
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1007/978-3-662-47709-0_6
-
dc.description.numberOfPages
12
-
tuw.event.name
WoLLIC 2015
-
tuw.event.startdate
20-07-2015
-
tuw.event.enddate
23-07-2015
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Bloomington, USA
-
tuw.event.place
Bloomington, USA
-
tuw.event.country
NON-EU
-
tuw.event.presenter
de Haan, Ronald
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.presentation.type
science to science/art to art
-
item.grantfulltext
none
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openairetype
conference paper
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen