Tree adjunct grammars

DOI10.1016/S0022-0000(75)80019-5zbMath0326.68053OpenAlexW2130630493MaRDI QIDQ1225947

Leon S. Levy, Masako Takahashi, Aravind K. Joshi

Publication date: 1975

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(75)80019-5

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments. ⋮ On Tree Substitution Grammars ⋮ The grammar of mammalian brain capacity ⋮ Linearity and nondeletion on monadic context-free tree grammars ⋮ Boolean grammars ⋮ Algebraic dynamic programming for multiple context-free grammars ⋮ Input-driven languages are linear conjunctive ⋮ On parsing coupled-context-free languages ⋮ LR(k)-coupled-context-free grammars ⋮ Fully generated scripted dialogue for embodied agents ⋮ Pumping lemmas for the control language hierarchy ⋮ The equivalence of four extensions of context-free grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Sample Selection for Statistical Parsing ⋮ Discriminative Reranking for Natural Language Parsing ⋮ Tree-Local Multicomponent Tree-Adjoining Grammars with Shared Nodes ⋮ Grammatical verification for mathematical formula recognition based on context-free tree grammar ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ Learning Tree Languages ⋮ The equivalence of tree adjoining grammars and monadic linear context-free tree grammars ⋮ Lexicalized non-local MCTAG with dominance links is NP-complete ⋮ Natural Language Processing, Moving from Rules to Data ⋮ On the complexity of 2-monotone restarting automata ⋮ On multiple context-free grammars ⋮ Fast uniform analysis of Coupled-Context-Free languages ⋮ Context-free grammars with lookahead ⋮ Linear time parsers for classes of non context free languages ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Graph grammars according to the type of input and manipulated data: a survey ⋮ Parallel parsing of tree adjoining grammars on the connection machine ⋮ An NC algorithm for recognizing tree adjoining languages ⋮ A geometric hierarchy beyond context-free languages ⋮ BUILDING RANDOM TREES FROM BLOCKS ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Geometric representations for minimalist grammars ⋮ A principled approach to grammars for controlled natural languages and predictive editors ⋮ On the membership problem for non-linear abstract categorial grammars ⋮ Augmented transition networks and their relation to tree transducers ⋮ Associative language descriptions ⋮ Associative grammar combination operators for tree-based grammars ⋮ Two complementary operations inspired by the DNA hairpin formation: Completion and reduction ⋮ Two Equivalent Regularizations for Tree Adjoining Grammars ⋮ TAL recognition in \(O(M(n^2))\) time ⋮ Highly constrained unification grammars ⋮ Tree adjoining grammars for RNA structure prediction ⋮ Characterizations of recursively enumerable languages by means of insertion grammars ⋮ Tree adjunct languages as integer set recognizers† ⋮ CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS ⋮ Semi-linearity, Parikh-boundedness and tree adjunct languages ⋮ Categorial dependency grammars ⋮ wMSO theories as grammar formalisms

Cites Work