Сызықтық Контекстсіз Қайта Жазу Жүйелері
Related Papers
Characterizing Structural Descriptions Produced by Various Grammatical Formalisms
We consider the structural descriptions produced by vari- ous grammatical formalisms in ~ of the complexity of the paths and the relationship between paths in the sets of structural descriptions …...
Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems
Recent results have established that there is a family of languages that is exactly the class of languages generated by three independently developed grammar formalisms: Tree Adjoining Grammm~, Head Grammars, …...
Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems
Linear Context-free Rewriting Systems (LCFRS) is an expressive grammar formalism with applications in syntax-based machine translation. The parsing complexity of an LCFRS is exponential in both the rank of a …...
Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two
Linear Context-Free Rewriting Systems (LCFRSs) are a grammar formalism ca- pable of modeling discontinuous phrases. Many parsing applications use LCFRSs where the fan-out (a measure of the dis- continuity of …...
Efficient parsing with Linear Context-Free Rewriting Systems
Previous work on treebank parsing with discontinuous constituents using Linear Context-Free Rewriting systems (LCFRS) has been limited to sentences of up to 30 words, for reasons of computational com- plexity. …...
Conversation Trees: A Grammar Model for Topic Structure in Forums
Online forum discussions proceed differ- ently from face-to-face conversations and any single thread on an online forum con- tains posts on different subtopics. This work aims to characterize the content …...
Generic refinement of expressive grammar formalisms with an application to discontinuous constituent parsing
AbstractWe formulate a generalization of Petrov et al. (2006)’s split/merge algorithm for interpreted regular tree grammars (Koller and Kuhlmann, 2011), which capture a large class of grammar formalisms. We evaluate …...