Exploring a Scalable and Evolutionary Formalisation on Tree Adjoining Grammars

Abstract

Tree adjoining grammars (TAGs) are psycholinguistic formalisms proposed by Prof. newlineArvind Joshi from University of Pennsylvania. These formalism are special in the way newlinethey generate tree languages with complex deep structure. They fall under the class newlineof mildly context sensitive grammars. They were originally used to model and mimic newlinenatural language syntax for purposes such as machine translation, dependency parsing newlineand understanding deep structure. Unlike context free grammars on which most of newlinethe computer programming languages are based on, tree adjoining grammars are aware newlineof contextual information and capture dependencies between lexicons (words) that are newlinefar away in the original sentence. They can also separate recurring structures such as newlinerepeating adjectives or nouns into single tree productions that have a recurring root newlineand a foot node; such recurring trees are called auxiliary trees and are literally inserted newlineinto other tree forms by exploding any matching node into root and foot node. This newlineprocess of insertion of trees is called an adjunction; it is this particular operation used newlineto combine trees, that makes it, mildly context sensitive. In this day and age of machine newlinelearning and deep learning, tree adjoining grammars remain relevant as they contribute newlineto our understanding of linguistic and other deep structure cognition. Parsing such a newlinegrammar that generates trees rather than strings is quite complex to imagine. However newlineconsiderable work has been done in this area and multiple parsing algorithms of newlinevarying efficiencies have been proposed; including machine learned models. Most of these newlinealgorithms also have robust implementations. The parsing process generates another newlinetree structure called a derivation. This structure is of vital importance when analysing newlinephrase structures. Since natural languages are finitely ambiguous, tree adjoining gram- newlinemars are ideal to model them. But despite best efforts and numerous algorithms tree newlineadjoining grammar parsing is a hard problem with the worst case complexity...