Optimality parsing and local cost functions in Discontinuous Grammar

After a brief survey of Discontinuous Grammar (DG), we propose local cost functions as a generalization of violable constraints in OT, probabilities in PCFG, and processing times in distributed competition models. We demonstrate how local cost functions can be used in DG to encode violable constraints on word order, landing sites, islands, agreement, and selectional restrictions, as well as lexical frequencies and pragmatic preferences. Rephrasing parsing as an optimization problem in which a large space of partial parses is searched for a minimum-cost solution, we propose a heuristic parsing algorithm for DG based on local search, with worst-case complexity O(nlog4n) given linguistically reasonable assumptions on tree depth and island constraints, and O(n5) without any assumptions. The proposed algorithm works in the presence of local ambiguity, produces the right analysis for a wide range of discontinuous word-order phenomena such as topicalizations, relativizations, extractions, scramblings, and discontinuous APs, and fails on garden-path sentences, just like humans.