Tree adjoining languages

The language MIX consists of all strings over the threeletter alphabet {a, b, c} that contain an equal number of occurrences of each letter. We prove Joshi’s (1985) conjecture that MIX is not a treeadjoining language. 1 Introduction The language MIX = { w ∈ {a, b, c}∗  wa = wb = wc } has attracted considerable attention in computational linguistics.
9p nghetay_1 07042013 30 1 Download

We define a set of deterministic bottomup left to right parsers which analyze a subset of Tree Adjoining Languages. The LR parsing strategy for Context Free Grammars is extended to Tree Adjoining Grammars (TAGs). We use a machine, called Bottomup Embedtied Push Down Automaton (BEPDA), that recognizes in a bottomup fashion the set of Tree Adjoining Languages (and exactly this se0. Each parser consists of a finite state control that drives the moves of a Bottomup Embedded Pushdown Automaton. ...
8p bungio_1 03052013 27 1 Download

Several methods are known for parsing languages generated by Tree Adjoining Grammars (TAGs) in O(n 6) worst case running time. In this paper we investigate which restrictions on TAGs and TAG derivations are needed in order to lower this O(n 6) time complexity, without introducing large runtime constants, and without losing any of the generative power needed to capture the syntactic constructions in natural language that can be handled by unrestricted TAGs.
7p bunrieu_1 18042013 31 2 Download

Since the early Sixties and Seventies it has been known that the regular and contextfree languages are characterized by definability in the monadic secondorder theory of certain structures. More recently, these descriptive characterizations have been used to obtain complexity results for constraint and principlebased theories of syntax and to provide a uniform modeltheoretic framework for exploring the relationship between theories expressed in disparate formal terms.
5p bunrieu_1 18042013 41 2 Download

Language models for speech recognition typically use a probability model of the form Pr(an[al,a2,...,ani). Stochastic grammars, on the other hand, are typically used to assign structure to utterances, A language model of the above form is constructed from such grammars by computing the prefix probability ~we~* Pr(al..artw), where w represents all possible terminations of the prefix al...an. The main result in this paper is an algorithm to compute such prefix probabilities given a stochastic Tree Adjoining Grammar (TAG). The algorithm achieves the required computation in O(n 6) time. ...
7p bunrieu_1 18042013 31 2 Download

The precise formulation of derivation for treeadjoining grammars has important ramifications for a wide variety of uses of the formalism, from syntactic analysis to semantic interpretation and statistical language modeling. We argue that the definition of treeadjoining derivation must be reformulated in order to manifest the proper linguistic dependencies in derivations. The particular proposal is both precisely characterizable, through a compilation to linear indexed grammars, and computationally operational, by virtue of an efficient algorithm for recognition and parsing. ...
10p bunmoc_1 20042013 33 2 Download

We examine the relationship between the two grammatical formalisms: Tree Adjoining Grammars and Head Grammars. We briefly investigate the weak equivalence of the two formalisms. We then turn to a discussion comparing the linguistic expressiveness of the two formalisms.
8p bungio_1 03052013 20 2 Download

Taking examples from English and French idioms, this paper shows that not only constituent structures rules but also most syntactic rules (such as topicalization, whquestion, pronominalization ...) are subject to lexical constraints (on top of syntactic, and possibly semantic, ones). We show that such puzzling phenomena are naturally handled in a 'lexJcalized' formalism such as Tree Adjoining Grammar. The extended domain of locality of TAGs also allows one to 'lexicalize' syntactic rules while defining them at the level of constituent structures. ...
7p bungio_1 03052013 24 2 Download

We present an algorithm for simultaneously constructing both the syntax and semantics of a sentence using a Lexicalized Tree Adjoining Grammar (LTAG). This approach captures naturally and elegantly the interaction between pragmatic and syntactic constraints on descriptions in a sentence, and the inferential interactions between multiple descriptions in a sentence. At the same time, it exploits linguistically motivated, declarative specifications of the discourse functions of syntactic constructions to make contextually appropriate syntactic choices. ...
8p bunthai_1 06052013 35 2 Download

Scrambling, both local and longdistance, has recently attracted considerable attention among linguists and computational linguists. In this paper, we will explore the adequacy of the Tree Adjoining Grammar (TAG) formalism for dealing with longdistance scrambling I in German. We will show that TAGs cannot capture the full range of constructions derived by scrambling. I[owever, MultiComponent TAGs (MCTAG), an extension of TAGs introduced earlier [Joshi 1987a, Weir 1988] and utilized for linguistic purposes (e.g.
6p buncha_1 08052013 26 2 Download

In this paper a bidirectional parser for Lexicalized Tree Adjoining Grammars will be presented. The algorithm takes advantage of a peculiar characteristic of Lexicalized TAGs, i.e. that each elementary tree is associated with a lexical item, called its anchor. The algorithm employs a mixed strategy: it works bottomup from the lexical anchors and then expands (partial) analyses making topdown predictions.
6p buncha_1 08052013 41 2 Download

We study parsing of tree adjoining grammars with particular emphasis on the use of shared forests to represent all the parse trees deriving a wellformed string. We show that there are two distinct ways of representing the parse forest one of which involves the use of linear indexed grammars and the other the use of contextfree grammars. The work presented in this paper is intended to give a general framework for studying tag parsing.
10p buncha_1 08052013 22 2 Download

Recently, it was shown (K UHLMANN , S ATTA: Treeadjoining grammars are not closed under strong lexicalization. Comput. Linguist., 2012) that ﬁnitely ambiguous tree adjoining grammars cannot be transformed into a normal form (preserving the generated tree language), in which each production contains a lexical symbol.
10p nghetay_1 07042013 27 1 Download

Synchronous TreeAdjoining Grammar (STAG) is a promising formalism for syntaxaware machine translation and simultaneous computation of naturallanguage syntax and semantics. Current research in both of these areas is actively pursuing its incorporation. However, STAG parsing is known to be NPhard due to the potential for intertwined correspondences between the linked nonterminal symbols in the elementary structures.
9p hongphan_1 15042013 30 1 Download

Tree Adjoining G r a m m a r (TAG) is u formalism for natural language grammars. Some of the basic notions of T A G ' s were introduced in [Jo~hi,Levy, mad Takakashi I~'Sl and by [Jo~hi, l ~ l . A detailed investigation of the linguistic relevance of T A G ' s has been carried out in IKroch and Joshi,1985~. In this paper, we will describe some new results for TAG's, espe¢ially in the following areas: (I) parsing complexity of TAG's, (2) some closure results for TAG's, and (3) the relationship to Head grammars. ...
12p bungio_1 03052013 27 1 Download

This paper presents an implemented, psychologically plausible parsing model for Government Binding theory grammars. I make use of two main ideas: (1) a generalization of the licensing relations of [Abney, 1986] allows for the direct encoding of certain principles of grammar (e.g. Theta Criterion, Case Filter) which drive structure building; (2) the working space of the parser is constrained to the domain determined by a Tree Adjoining Grammar elementary tree. All dependencies and constraints are locaiized within this bounded structure. ...
8p bungio_1 03052013 25 1 Download

In the literature, Tree Adjoining Grammars (TAGs) are propagated to be adequate for natural language description   analysis as well as generation. In this paper we concentrate on the direction of analysis. Especially important for an implementation of that task is how efficiently this can be done, i.e., how readily the word problem can be solved for TAGs. Up to now, a parser with O(n 6) steps in the worst case was known where n is the length of the input string. In this paper, the result is improved to O(n 4 log n) as a new lowest...
8p bungio_1 03052013 24 1 Download

We place synchronous treeadjoining grammars and tree transducers in the single overarching framework of bimorphisms, continuing the uniﬁcation of synchronous grammars and tree transducers initiated by Shieber (2004). Along the way, we present a new deﬁnition of the treeadjoining grammar derivation relation based on a novel direct interreduction of TAG and monadic macro tree transducers.
8p bunthai_1 06052013 30 1 Download

Much of the power of probabilistic methods in modelling language comes from their ability to compare several derivations for the same string in the language. An important starting point for the study of such crossderivational properties is the notion of consistency. The probability model defined by a probabilistic grammar is said to be consistent if the probabilities assigned to all the strings in the language sum to one.
7p bunrieu_1 18042013 35 3 Download

There is increasing recognition of the fact that the entire range of dependencies that transformational grammars in their various incarnations h a v e t r i e d t o a c c o u n t f o r c a n be satisfactorily captured by classes of rules that are nontransformational and at the same Clme highly constrlaned in terms of the classes of grammars and languages that they define .
9p bungio_1 03052013 29 3 Download