Chris Brew suggested I actually explain what it is I meant:  here is a sample paper on phase transitions in solving problems like 3-sat:<br><br><a href="http://www.sciencemag.org/cgi/content/abstract/264/5163/1297">http://www.sciencemag.org/cgi/content/abstract/264/5163/1297</a><br>

<br>Props to Chris!<br><br>Miles<br><br><div><span class="gmail_quote">On 04/02/2008, <b class="gmail_sendername">Miles Osborne</b> <<a href="mailto:miles@inf.ed.ac.uk">miles@inf.ed.ac.uk</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

I must confess, the idea that a corpus can be described in terms of "parseability" sounds a little ill-founded to me.  The choice of particular parsing algorithm may dictate which examples are hard to process, as will the underlying grammar etc etc.  <br>

<br>What would be interesting (read:  hard) would be to look at the work on phase transitions in 3-sat problems and the like.  So, are there underlying graph-related characteristics of parsing which make certain sentences intrinsically hard to process and in particular can these characteristics be framed in a manner that was independent of the actual parser.   <br>

<br>Miles<br clear="all"><span class="sg">

--  The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.

</blockquote></div> <br clear="all"> --  The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.