Natural language is a uniquely convenient means of communication due to, among its other properties, its flexibility and its openness to interpretation. These properties of natural language are largely made possible by its heavy dependence on context and common ground. Drawing on elements of Clark’s account of language use, we view natural language interactions as a coordination problem involving agents who work together to convey and thus coordinate their interaction goals. In the modeling work presented here, a sequence of interrelated modules developed in the Polyscheme cognitive architecture is used to implement several stages of reasoning the user of a simple video application would expect an addressee—ultimately, the application—to work through, if the interaction goal was to locate a scene they had previously viewed together.

Many important tasks can be cast as weighted relational satisfiability problems.  Propositionalizing relational theories and making inferences with them using SAT algorithms has proven effective in many cases.  However, these approaches require that all objects in a domain be known in advance.  Many domains, from language understanding to machine vision, involve reasoning about objects that are not known beforehand.  Theories with unknown objects can require models with infinite objects in their domain and thus lead to propositionalized SAT theories that existing algorithms cannot deal with.  To address these problems, we characterize a class of relational generative weighted satisfiability theories (GenSAT) over potentially infinite domains and propose an algorithm, GenDPLL, for finding models of these theories.  We introduce the notion of a relevant model and an increasing cost theory to identify conditions under which GenDPLL is complete, even when a theory has infinite models.