Semantic Evaluation as Constraint Network Consistency

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Constraint Satisfaction

This paper investigates a problem of natural language processing from the perspective of reasoning work on constraint satisfaction. We formulate the task of computing singular, definite reference to a known contextual entity as a constraint satisfaction problem. We argue that such referential constraint problems have a structure which is often simpler than the general case, and can therefore often be solved by the sole use of low-power network consistency techniques. To illustrate, we define a linguistic fragment which provably generates tree-structured constraint problems. This enables us to conclude that the limited operation of strong arc consistency is sufficient to resolve the class of noun phrase defined by the fragment.