Easy Solutions for a Hard Problem? The Computational Complexity of Reciprocals with Quantificational Antecedents

We report two experiments which tested whether cognitive capacities are limited to those functions that are computationally tractable (PTIME-Cognition Hypothesis). In particular, we investigated the semantic processing of reciprocal sentences with generalized quantifiers, i.e., sentences of the form...

Full description

Saved in:
Bibliographic Details
Published in:Journal of logic, language, and information language, and information, 2013-12, Vol.22 (4), p.363-390
Main Authors: Schlotterbeck, Fabian, Bott, Oliver
Format: Article
Language:English
Subjects:
Computational complexity
Computational linguistics
Criminal sentencing
Education
Information Systems Applications (incl.Internet)
Language
Lexical quantifiers
Logic
Logical antecedents
Modeling
Natural language
Philosophy
Semantics
Truth condition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We report two experiments which tested whether cognitive capacities are limited to those functions that are computationally tractable (PTIME-Cognition Hypothesis). In particular, we investigated the semantic processing of reciprocal sentences with generalized quantifiers, i.e., sentences of the form Q dots are directly connected to each other, where Q stands for a generalized quantifier, e.g. all or most. Sentences of this type are notoriously ambiguous and it has been claimed in the semantic literature that the logically strongest reading is preferred (Strongest Meaning Hypothesis). Depending on the quantifier, the verification of their strongest interpretations is computationally intractable whereas the verification of the weaker readings is tractable. We conducted a picture completion experiment and a picture verification experiment to investigate whether comprehenders shift from an intractable reading to a tractable reading which should be dispreferred according to the Strongest Meaning Hypothesis. The results from the picture completion experiment suggest that intractable readings occur in language comprehension. Their verification, however, rapidly exceeds cognitive capacities in case the verification problem cannot be solved using simple heuristics. In particular, we argue that during verification, guessing strategies are used to reduce computational complexity.
ISSN:0925-8531
1572-9583
DOI:10.1007/s10849-013-9181-9