ACG parsing: the general case

Philippe De Groote

Colloquium in Honor of Gérard Huet, Paris 22-23 June 2007

An abstract categorial grammar (ACG) consists of two higher-order signatures together with a linear morphism that maps the well-typed linear lambda-terms built on the first signature to well-typed linear lambda-terms built on the second signature. Parsing with an ACG amounts to inverting this morphism. In the second-order case, Makoto Kanazawa's has shown that such parsing problems may be reduced to datalog queries. We generalize his result by showing how ACG parsing may be reduced to a linear logic proof-search problem.