Despite wide variation among natural languages, there are lin-guistic properties universal to all (or nearly all) languages. Animportant challenge is to explain why these linguistic universalshold. One explanation employs a learnability argument: seman-tic universals hold because expressions that satisfy them areeasier to learn than those that do not. In an exploratory studywe investigate the relation between learnability and complexityand whether the presence of semantic universals for quantifierscan also be explained by differences in complexity. We developa novel application of (approximate) Kolmogorov complexityto measure fine-grained distinctions in complexity between dif-ferent quantifiers. Our results indicate that the monotonicityuniversal can be explained by complexity while the conserva-tivity universal cannot. For quantity we did not find a robustresult. We also found that learnability and complexity patterntogether in the monotonicity and conservativity cases that weconsider, while that pattern is less robust in the quantity cases.

Deductive Mastermind is a deductive reasoning game that isimplemented in the online educational game system Math Gar-den. A good understanding of the difficulty of Deductive Mas-termind game instances is essential for optimizing the learningexperience of players. The available empirical difficulty rat-ings, based on speed and accuracy, provide robust estimationsbut do not explain why certain game instances are easy or hard.In previous work a logic-based model was proposed that suc-cessfully predicted these difficulty ratings. We add to this workby providing a model based on a different logical principle—that of eliminating hypotheses (dynamic epistemic logic) in-stead of reasoning by cases (analytical tableaux system)—thatcan predict the empirical difficulty ratings equally well. Weshow that the informational content of the different feedbacksgiven in game instances is a core predictor for cognitive dif-ficulty ratings and that this is irrespective of the specific logicused to formalize the game.

Despite wide variation among natural languages, there are linguistic properties thought to be universal to all or almost all natural languages. Here, we consider universals at the semantic level, in the domain of quantifiers, which are given by the properties of monotonicity, quantity, and conservativity. We investigate whether these universals might be explained by differences in complexity. We generate a large collection of quantifiers, based on a simple yet expressive grammar, and compute both their complexities and whether they adhere to these universal properties. We find that quantifiers satisfying semantic universals are less complex: they have a shorter minimal description length.