Scipediacontent: Scipediacontent moved page Draft Content 965190169 to Hollingshead Roark 2010a

2021-01-28T23:36:14Z

Scipediacontent moved page Draft Content 965190169 to Hollingshead Roark 2010a

Scipediacontent: Created page with " == Abstract == In this paper, we extend methods from Roark and Hollingshead (2008) for reducing the worst-case complexity of a context-free parsing pipeline via hard constra..."

2021-01-28T23:36:09Z

Created page with " == Abstract == In this paper, we extend methods from Roark and Hollingshead (2008) for reducing the worst-case complexity of a context-free parsing pipeline via hard constra..."

New page

== Abstract ==

In this paper, we extend methods from Roark and Hollingshead (2008) for reducing the worst-case complexity of a context-free parsing pipeline via hard constraints derived from finite-state tagging pre-processing. Methods from our previous paper achieved quadratic worst-case complexity. We prove here that alternate methods for choosing constraints can achieve either linear or O(Nlog2N) complexity. These worst-case bounds on processing are demonstrated to be achieved without reducing the parsing accuracy, in fact in some cases improving the accuracy. The new methods achieve observed performance comparable to the previously published quadratic complexity method. Finally, we demonstrate improved performance by combining complexity bounding methods with additional high precision constraints.

== Original document ==

The different versions of the original document can be found in:

* [http://dl.acm.org/ft_gateway.cfm?id=1620849&type=pdf http://dl.acm.org/ft_gateway.cfm?id=1620849&type=pdf]

* [http://dx.doi.org/10.3115/1620754.1620849 http://dx.doi.org/10.3115/1620754.1620849]

* [https://www.aclweb.org/anthology/N09-1073.pdf https://www.aclweb.org/anthology/N09-1073.pdf],
: [https://core.ac.uk/display/22965468 https://core.ac.uk/display/22965468],
: [https://www.aclweb.org/anthology/N09-1073 https://www.aclweb.org/anthology/N09-1073],
: [https://dblp.uni-trier.de/db/conf/naacl/naacl2009.html#RoarkH09 https://dblp.uni-trier.de/db/conf/naacl/naacl2009.html#RoarkH09],
: [https://dl.acm.org/citation.cfm?id=1620754.1620849 https://dl.acm.org/citation.cfm?id=1620754.1620849],
: [https://www.cs.brandeis.edu/~marc/misc/proceedings/naacl-hlt-2009/NAACLHLT09/pdf/NAACLHLT09073.pdf https://www.cs.brandeis.edu/~marc/misc/proceedings/naacl-hlt-2009/NAACLHLT09/pdf/NAACLHLT09073.pdf],
: [https://academic.microsoft.com/#/detail/2018341884 https://academic.microsoft.com/#/detail/2018341884]

← Older revision	Revision as of 23:36, 28 January 2021
(No difference)

Hollingshead Roark 2010a - Revision history

Scipediacontent: Scipediacontent moved page Draft Content 965190169 to Hollingshead Roark 2010a

Scipediacontent: Created page with " == Abstract == In this paper, we extend methods from Roark and Hollingshead (2008) for reducing the worst-case complexity of a context-free parsing pipeline via hard constra..."