Article Structure
Abstract
Linear Context-Free Rewriting Systems (LCFRSs) are a grammar formalism capable of modeling discontinuous phrases.
Introduction
Linear Context-Free Rewriting Systems (LCFRSs) have been introduced by Vijay-Shanker et al.
LCFRSS
In this section we introduce the basic notation for LCFRS and the notion of production factorization.
A graph-based representation for LCFRS productions
Rather than factorizing LCFRS productions directly, in this article we work with a more abstract representation of productions based on graphs.
The algorithm
In this section we provide an efficient, recursive algorithm for the decomposition of a p-graph into bundles, which corresponds to factorizing the represented LCFRS production.
Time complexity analysis
In Section 4, we claimed that there are no more than (9(n2) bundles.
Conclusion
We have introduced an efficient algorithm for optimal reduction of the rank of LCFRSs with fanout at most 2, that runs in quadratic time w.r.t.
Topics
time complexity
- In this section we sketch the proof of this result, which will prove the quadratic time complexity of our algorithm.Page 8, “Time complexity analysis”
- Our induction hypothesis is that for m < n, the time complexity is in (9(m2).Page 8, “Time complexity analysis”
- Given the fact that fanout l bundles can be attached to any adjacent bundle in our factorization, we can show that our algorithm also optimizes time complexity for known tabular parsing algorithms for LCFRSs with fanout 2.Page 9, “Conclusion”
- As for general LCFRS, it has been shown by Gildea (2010) that rank optimization and time complexity optimization are not equivalent.Page 9, “Conclusion”
- Furthermore, all known algorithms for rank or time complexity optimization have an exponential time complexity (Gomez-Rodriguez et al., 2009).Page 9, “Conclusion”
See all papers in Proc. ACL 2010 that mention time complexity.
See all papers in Proc. ACL that mention time complexity.
Back to top.
binarization
- Most of the literature has been focusing on binarization algorithms, which attempt to find a reduction to 7“ = 2 and return a failure if this is not possible.Page 1, “Introduction”
- (2009) report a general binarization algorithm for LCFRS which, in the case of f = 2, works in time 0(lpl7), where |p| is the size of the input production.Page 1, “Introduction”
- A more efficient binarization algorithm for the case f = 2 is presented in (Gomez-Rodriguez and Satta, 2009), working in time O(|p|).Page 1, “Introduction”
See all papers in Proc. ACL 2010 that mention binarization.
See all papers in Proc. ACL that mention binarization.
Back to top.
ccg
- If x1 and cc2 do not occur both in the same string yl or 3/2, then we say that there is a gap between cc1 and ccg .Page 4, “A graph-based representation for LCFRS productions”
- If cc1 <p cc2 and there is no gap between cc1 and ccg, then we write [cc1, ccg] to denote the set {cc1,cc2} U{cc|cc E V},, cc1 <}, c <}, ccg }.Page 4, “A graph-based representation for LCFRS productions”
- Note that the first condition means that 7“ and 7“’ are disjoint sets and, for any pair of vertices c E 7“ and cc’ E 7“’, either there is a gap between cc and cc’ or else there exists some ccg E V}, such that 9c <p ccg <p Jc’andflcg E’TUT’.Page 4, “A graph-based representation for LCFRS productions”
See all papers in Proc. ACL 2010 that mention ccg.
See all papers in Proc. ACL that mention ccg.
Back to top.
parsing algorithms
- This results in asymptotical running time improvement for known parsing algorithms for this class.Page 1, “Abstract”
- Under a theoretical perspective, the parsing problem for LCFRSS with f = 2 is NP-complete (Satta, 1992), and in known parsing algorithms the running time is exponentially affected by the rank 7“ of the grammar.Page 1, “Introduction”
- Given the fact that fanout l bundles can be attached to any adjacent bundle in our factorization, we can show that our algorithm also optimizes time complexity for known tabular parsing algorithms for LCFRSs with fanout 2.Page 9, “Conclusion”
See all papers in Proc. ACL 2010 that mention parsing algorithms.
See all papers in Proc. ACL that mention parsing algorithms.
Back to top.
