A dichotomy result for Ramsey quantifiers

DOI10.1007/978-3-662-47709-0_6MaRDI QIDQ2947460zbMATH OpenOpenAlexFDO

Authors Ronald de Haan, Jakub Szymanik

Publication date 24 September 2015

Published in Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47709-0_6

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Descriptive complexity and finite models (68Q19)

Recommendations

• Characterizing polynomial Ramsey quantifiers
• Dichotomy result for independence-friendly prefixes of generalized quantifiers
• A dichotomy in classifying quantifiers for finite models
• Logical hierarchies in PTIME
• scientific article; zbMATH DE number 3873306

Cites work

• Computational complexity of the semantics of some natural language constructions
• Definability of polyadic lifts of generalized quantifiers
• Dichotomy result for independence-friendly prefixes of generalized quantifiers
• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents
• Finite model theory and its applications.
• Henkin quantifiers and complete problems
• Henkin quantifiers: logic, games, and computation.
• scientific article; zbMATH DE number 6003856 (Why is no real title available?)
• Lower bounds based on the exponential time hypothesis
• On the complexity of k-SAT
• On the Structure of Polynomial Time Reducibility
• Parametrized complexity theory.
• Strong computational lower bounds via parameterized complexity
• The complexity of satisfiability problems
• The inapproximability of non-NP-hard optimization problems.
• Tight lower bounds for certain parameterized NP-hard problems
• Unary quantifiers on finite models

Cited in

(12)

• A new approach to the Ramsey-type games and the Gowers dichotomy in \(F\)-spaces
• A parametrization of the abstract Ramsey theorem
• Ramsey functions for quasi-progressions with large diameter
• A recursion theoretic analysis of the clopen Ramsey theorem
• A Ramsey-Type Result for Convex Sets
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• scientific article; zbMATH DE number 1420849 (Why is no real title available?)
• scientific article; zbMATH DE number 1453081 (Why is no real title available?)
• Dichotomy result for independence-friendly prefixes of generalized quantifiers
• Characterizing polynomial Ramsey quantifiers
• Ramsey theory for countable binary homogeneous structures
• Borel separability of the coanalytic Ramsey sets

This page was built for publication: A dichotomy result for Ramsey quantifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947460)