Tree adjoining languages

Xem 1-20 trên 38 kết quả Tree adjoining languages
  • The language MIX consists of all strings over the three-letter 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 tree-adjoining language. 1 Introduction The language MIX = { w ∈ {a, b, c}∗ | |w|a = |w|b = |w|c } has attracted considerable attention in computational linguistics.

    pdf9p nghetay_1 07-04-2013 30 1   Download

  • We define a set of deterministic bottom-up 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 Bottom-up Embedtied Push Down Automaton (BEPDA), that recognizes in a bottom-up 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 Bottom-up Embedded Pushdown Automaton. ...

    pdf8p bungio_1 03-05-2013 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.

    pdf7p bunrieu_1 18-04-2013 31 2   Download

  • Since the early Sixties and Seventies it has been known that the regular and context-free languages are characterized by definability in the monadic second-order theory of certain structures. More recently, these descriptive characterizations have been used to obtain complexity results for constraint- and principle-based theories of syntax and to provide a uniform model-theoretic framework for exploring the relationship between theories expressed in disparate formal terms.

    pdf5p bunrieu_1 18-04-2013 41 2   Download

  • Language models for speech recognition typically use a probability model of the form Pr(an[al,a2,...,an-i). 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 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. ...

    pdf7p bunrieu_1 18-04-2013 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 tree-adjoining 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. ...

    pdf10p bunmoc_1 20-04-2013 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.

    pdf8p bungio_1 03-05-2013 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, wh-question, 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. ...

    pdf7p bungio_1 03-05-2013 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. ...

    pdf8p bunthai_1 06-05-2013 35 2   Download

  • Scrambling, both local and long-distance, 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 long-distance scrambling I in German. We will show that TAGs cannot capture the full range of constructions derived by scrambling. I[owever, Multi-Component TAGs (MC-TAG), an extension of TAGs introduced earlier [Joshi 1987a, Weir 1988] and utilized for linguistic purposes (e.g.

    pdf6p buncha_1 08-05-2013 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 bottom-up from the lexical anchors and then expands (partial) analyses making top-down predictions.

    pdf6p buncha_1 08-05-2013 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 well-formed 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 context-free grammars. The work presented in this paper is intended to give a general framework for studying tag parsing.

    pdf10p buncha_1 08-05-2013 22 2   Download

  • Recently, it was shown (K UHLMANN , S ATTA: Tree-adjoining grammars are not closed under strong lexicalization. Comput. Linguist., 2012) that finitely ambiguous tree adjoining grammars cannot be transformed into a normal form (preserving the generated tree language), in which each production contains a lexical symbol.

    pdf10p nghetay_1 07-04-2013 27 1   Download

  • Synchronous Tree-Adjoining Grammar (STAG) is a promising formalism for syntaxaware machine translation and simultaneous computation of natural-language syntax and semantics. Current research in both of these areas is actively pursuing its incorporation. However, STAG parsing is known to be NP-hard due to the potential for intertwined correspondences between the linked nonterminal symbols in the elementary structures.

    pdf9p hongphan_1 15-04-2013 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. ...

    pdf12p bungio_1 03-05-2013 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. ...

    pdf8p bungio_1 03-05-2013 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...

    pdf8p bungio_1 03-05-2013 24 1   Download

  • We place synchronous tree-adjoining grammars and tree transducers in the single overarching framework of bimorphisms, continuing the unification of synchronous grammars and tree transducers initiated by Shieber (2004). Along the way, we present a new definition of the tree-adjoining grammar derivation relation based on a novel direct inter-reduction of TAG and monadic macro tree transducers.

    pdf8p bunthai_1 06-05-2013 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 cross-derivational 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.

    pdf7p bunrieu_1 18-04-2013 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 non-transformational and at the same Clme highly constrlaned in terms of the classes of grammars and languages that they define .

    pdf9p bungio_1 03-05-2013 29 3   Download



p_strKeyword=Tree adjoining languages

nocache searchPhinxDoc


Đồng bộ tài khoản