Deductive parsers for LFG?

[Mark Johnson]

Hi John,

There are a number of excellent implementations of LFG around (including 
the one from Parc, of course), but that is not what you're asking about.

The main reason why there are no deductive parsers for LFG is that LFG 
has always been thought of in terms of satisfiability of constraints, 
rather than deductive inference from a set of axioms and inference 
rules.  As far as I know there's no principled reason why this should 
not be possible (c.f. my comment about finite satisfiability being 
equivalent to deduction below), but it just hasn't been done. 

There are technical issues to be solved, of course. Some are quite 
theoretical: e.g. first-order deduction is Turing complete, while 
first-order satisfiability is co-Turing complete (but LFG generally 
requires the satisfying models to be finite, and first-order finite 
satistfiability is Turing complete, just like deduction, see my "Two 
Ways of Formalizing Grammars" in Linguistics and Philosophy 1994, which 
actually discusses LFG parsing). 

And there are practical problems in implementing a deductive parser for 
LFG which stem from the multiple levels of representation and diversity 
of constraints in LFG; arranging to coordinate these in a moderately 
efficient manner is complicated!

Best,

Mark Johnson

John Colby wrote:

> Does anyone know of deductive parsers for LFG, whether described as 
> per Shieber et. al (1994, 1995) or as parsing schemata as per 
> Sikkel(1993, 1997)
>
> Thank you,
> John
>
> *John E. Colby*
>
> *Ph.D. Candidate in Computer Science*
>
> *Baskin School of Engineering*
>
>  Baskin Engineering Building
>
>  University of California, Santa Cruz
>
>  1156 High St.
>
>  Santa Cruz, CA 95064
>
>  
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.linguistlist.org/pipermail/lfg/attachments/20051128/dc03332c/attachment.htm>