- Author:
- David Jeremy Weir,
- Supervisor:
- Aravind K. Joshi
This thesis involves the study of formal properties of grammatical formalisms that are relevant to computational linguists. The formalisms which will receive the most attention share the property that they are highly restricted in their generative power. Recent research suggests that Context-Free Grammars (CFG's) lack the necessary expressive power on which to base a linguistic theory. This has led computational linguists to consider grammatical formalisms whose generative power exceeds CFG's, but only to a limited extent. We compare a number of formalisms on the basis of their weak generative capacity, as well as suggesting ways in which they can be compared on the basis of their strong generative capacity. In particular, we consider properties of their structural descriptions (or tree sets); and the types of dependencies (nested, crossed, etc.) that can be exhibited by each formalism.
Several formalisms that are notationally quite different (Tree Adjoining Grammars, Head Grammars, and Linear Indexed Grammars) have been shown to be weakly equivalent. We show that Combinatory Categorical Grammars are weakly equivalent to these formalisms. The class of languages generated by these formalisms can be thought of one step up from CFG's, and we describe a number of progressions that illustrate this.
The string languages generated by TAL's, HL's, CCL's and LIL's exhibit limited crossed-serial dependencies in addition to those produced by Context-Free Grammars (nested and serial dependencies). By formalizing these crossed-serial dependencies and their relationship with the nested dependencies produced by CFG's we define an infinite progression of formalisms.
Our work on structural descriptions leads us to characterize a class of formalisms called Linear Context-Free Rewriting Systems (LCFRS's), which includes a wide range of grammatical formalisms with restricted power. The systems in this class have context-free derivations, and simple composition operations that are linear and nonerasing. We prove that all members of this family generate only semilinear languages that can be recognized in polynomial time.
Cited By
- Wedekind J and Kaplan R (2021). Tractable Lexical-Functional Grammar, Computational Linguistics, 46:3, (515-569), Online publication date: 1-Nov-2020.
- Tang H, Wang X, Zhang L, Xie B, Zhang L and Mei H (2015). Summary-Based Context-Sensitive Data-Dependence Analysis in Presence of Callbacks, ACM SIGPLAN Notices, 50:1, (83-95), Online publication date: 11-May-2015.
- Tang H, Wang X, Zhang L, Xie B, Zhang L and Mei H Summary-Based Context-Sensitive Data-Dependence Analysis in Presence of Callbacks Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, (83-95)
- Kanazawa M and Salvati S MIX is not a tree-adjoining language Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers - Volume 1, (666-674)
- van Cranenburgh A Efficient parsing with linear context-free rewriting systems Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, (460-470)
- Henderson J Bayesian network automata for modelling unbounded structures Proceedings of the 12th International Conference on Parsing Technologies, (63-74)
- Stabler E Top-down recognizers for MCFGs and MGs Proceedings of the 2nd Workshop on Cognitive Modeling and Computational Linguistics, (39-48)
- Zhang Y and Clark S Shift-reduce CCG parsing Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, (683-692)
- Kobele G and Michaelis J Disentangling notions of specifier impenetrability Proceedings of the 12th biennial conference on The mathematics of language, (126-142)
- Hockenmaier J and Bisk Y Normal-form parsing for combinatory categorial grammars with generalized composition and type-raising Proceedings of the 23rd International Conference on Computational Linguistics, (465-473)
- Chiang D Learning to translate with source and target syntax Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, (1443-1452)
- Kallmeyer L and Satta G A polynomial-time parsing algorithm for TT-MCTAG Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 2 - Volume 2, (994-1002)
- Nesson R and Shieber S Efficiently parsable extensions to tree-local multicomponent TAG Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, (92-100)
- Boullier P and Sagot B Multi-component tree insertion grammars Proceedings of the 14th international conference on Formal grammar, (31-46)
- Francez N and Kaminski M (2008). Commutation-augmented pregroup grammars and push-down automata with cancellation, Information and Computation, 206:9-10, (1018-1032), Online publication date: 1-Sep-2008.
- Chen-Main J and Joshi A Multi-component tree adjoining grammars, dependency graph models, and linguistic analyses Proceedings of the Workshop on Deep Linguistic Processing, (1-8)
- Kallmeyer L and Romero M Quantifier scope in German Proceedings of the Eighth International Workshop on Tree Adjoining Grammar and Related Formalisms, (73-80)
- Han C Pied-piping in relative clauses Proceedings of the Eighth International Workshop on Tree Adjoining Grammar and Related Formalisms, (41-48)
- Gärtner H and Michaelis J A note on the complexity of constraint interaction Proceedings of the 5th international conference on Logical Aspects of Computational Linguistics, (114-130)
- Kallmeyer L (2005). Tree-Local Multicomponent Tree-Adjoining Grammars with Shared Nodes, Computational Linguistics, 31:2, (187-226), Online publication date: 1-Jun-2005.
- Seddah D and Gaiffe B How to build argumental graphs using TAG shared forest Proceedings of the 5th international conference on Logical Aspects of Computational Linguistics, (287-300)
- Ljunglöf P A polynomial time extension of parallel multiple context-free grammar Proceedings of the 5th international conference on Logical Aspects of Computational Linguistics, (177-188)
- Melamed I, Satta G and Wellington B Generalized multitext grammars Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, (661-es)
- Rogers J Wrapping of trees Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, (558-es)
- Boullier P Range concatenation grammars New developments in parsing technology, (269-289)
- Harkema H A recognizer for minimalist languages New developments in parsing technology, (251-268)
- Groote P and Pogodalla S (2004). On the Expressive Power of Abstract Categorial Grammars, Journal of Logic, Language and Information, 13:4, (421-438), Online publication date: 29-Mar-2004.
- Castaño J (2004). Global Index Grammars and Descriptive Power, Journal of Logic, Language and Information, 13:4, (403-419), Online publication date: 29-Mar-2004.
- Castaño J GIGs Proceedings of the 4th international conference on Computational linguistics and intelligent text processing, (22-35)
- Hoai N, McKay R and Abbass H Tree adjoining grammars, language bias, and genetic programming Proceedings of the 6th European conference on Genetic programming, (335-344)
- Castaño J On the applicability of Global Index Grammars Proceedings of the 41st Annual Meeting on Association for Computational Linguistics - Volume 2, (15-22)
- Schuler W Using model-theoretic semantic interpretation to guide statistical parsing and word recognition in a spoken language interface Proceedings of the 41st Annual Meeting on Association for Computational Linguistics - Volume 1, (529-536)
- Joshi A Starting with complex primitives pays off Proceedings of the 4th international conference on Computational linguistics and intelligent text processing, (1-10)
- Chiang D and Joshi A Formal grammars for estimating partition functions of double-stranded chain molecules Proceedings of the second international conference on Human Language Technology Research, (63-67)
- Villemonte de la Clergerie É Parsing mildly context-sensitive languages with thread automata Proceedings of the 19th international conference on Computational linguistics - Volume 1, (1-7)
- Chiang D Constraints on strong generative power Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, (132-139)
- Ebert C and Kracht M Formal syntax and semantics of case stacking languages Proceedings of the 18th conference on Computational linguistics - Volume 1, (250-256)
- Schuler W, Chiang D and Dras M Multi-component TAG and notions of formal power Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, (448-455)
- Dras M A meta-level grammar Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, (80-87)
- Park H Mapping scrambled Korean sentences into English using synchronous tags Proceedings of the 33rd annual meeting on Association for Computational Linguistics, (317-319)
- Kulick S Using higher-order logic programming for semantic interpretation of coordinate constructs Proceedings of the 33rd annual meeting on Association for Computational Linguistics, (213-219)
- Groenink A Literal movement grammars Proceedings of the seventh conference on European chapter of the Association for Computational Linguistics, (90-97)
- Schabes Y and Waters R (1995). Tree insertion grammar, Computational Linguistics, 21:4, (479-513), Online publication date: 1-Dec-1995.
- Erbach G Bottom-up Earley deduction Proceedings of the 15th conference on Computational linguistics - Volume 2, (796-802)
- Hoffman B The formal consequences of using variables in CCG categories Proceedings of the 31st annual meeting on Association for Computational Linguistics, (298-300)
- Seki H, Nakanishi R, Kaji Y, Ando S and Kasami T Parallel multiple context-free grammars, finite-state translation systems, and polynomial-time recognizable subclasses of lexical-functional grammars Proceedings of the 31st annual meeting on Association for Computational Linguistics, (130-139)
- Schabes Y and Waters R Lexicalized context-free grammars Proceedings of the 31st annual meeting on Association for Computational Linguistics, (121-129)
- Vijay-Shanker K and Weir D (1993). Parsing some constrained grammar formalisms, Computational Linguistics, 19:4, (591-636), Online publication date: 1-Dec-1993.
- Rambow O A linguistic and computational analysis of the German "third construction" Proceedings of the 30th annual meeting on Association for Computational Linguistics, (297-299)
- Weir D Linear context-free rewriting systems and deterministic tree-walking transducers Proceedings of the 30th annual meeting on Association for Computational Linguistics, (136-143)
- Satta G Recognition of linear context-free rewriting systems Proceedings of the 30th annual meeting on Association for Computational Linguistics, (89-95)
- Becker T, Joshi A and Rambow O Long-distance scrambling and tree adjoining grammars Proceedings of the fifth conference on European chapter of the Association for Computational Linguistics, (21-26)
- Humphrey S and Krovetz B (1989). Selected M-Related Dissertations, ACM SIGART Bulletin:110, (58-64), Online publication date: 1-Oct-1989.
- Weir D and Joshi A Combinatory Categorial Grammars Proceedings of the 26th annual meeting on Association for Computational Linguistics, (278-285)
Recommendations
Mildly context-sensitive languages via buffer augmented pregroup grammars
Time for verificationA family of languages is called mildly context-sensitive if - it includes the family of all ε-free context-free languages; - it contains the languages • {anbncn : n ≥ 1} - multiple agreement, • {ambncmdn : m, n ≥ 1} - crossed dependencies, and • {ww : w ...
Mildly non-projective dependency grammar
Syntactic representations based on word-to-word dependencies have a long-standing tradition in descriptive linguistics, and receive considerable interest in many applications. Nevertheless, dependency syntax has remained something of an island from a ...
Towards Incremental Learning of Mildly Context-Sensitive Grammars
ICMLA '11: Proceedings of the 2011 10th International Conference on Machine Learning and Applications and Workshops - Volume 01Most models in grammatical inference have been restricted to regular or context-free grammars. As a step towards learning of more powerful grammars, this paper discusses the incremental learning of Linear Indexed Grammars (LIGs) for formal languages ...