Abstract
This paper classifies a family of grammar formalisms that extendcontext-free grammar by talking about tuples of terminal strings, ratherthan independently combining single terminal words into larger singlephrases. These include a number of well-known formalisms, such as headgrammar and linear context-free rewriting systems, but also a new formalism,(simple) literal movement grammar, which strictly extends the previouslyknown formalisms, while preserving polynomial time recognizability.
The descriptive capacity of simple literal movement grammars isillustrated both formally through a weak generative capacity argument and ina more practical sense by the description of conjunctive cross-serialrelative clauses in Dutch. After sketching a complexity result and drawing anumber of conclusions from the illustrations, it is then suggested that thenotion of mild context-sensitivity currently in use, that depends on therather loosely defined concept of constant growth, needs a modification toapply sensibly to the illustrated facts; an attempt at such a revision isproposed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chandra, A. K., D. C. Kozen, and L. J. Stockmeyer: 1981, ‘Alternation’, JACM 28, 114–133.
Ginsburg, S.: 1975, Formal Languages. North-Holland/Am. Elsevier, Amsterdam, Oxford/New York.
Groenink, Annius V.: 1995a, ‘Formal Mechanisms for Left Extraposition in Dutch’, in Proceedings of the 5th CLIN (Computational Linguistics in the Netherlands) meeting, November 1994, Enschede.
Groenink, Annius V.: 1995b, ‘Literal Movement Grammars’, in Proceedings of the 7th EA CL Conference, University College, Dublin.
Groenink, Annius V.: 1997, ‘Surface without Structure’, PhD thesis, University of Utrecht.
Hopcroft, J. E. and J. D. Ullman: 1979, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass.
Joshi, Aravind: 1985, ‘Tree Adjoining Grammars: How Much Context-Sensitivity is Required to Provide Reasonable Structural Descriptions?’ in A. Zwicky (ed.), Natural Language Parsing: Psychological, Computational and Theoretical Perspectives, Cambridge University Press, pp. 206–250.
Kaji, Y., R. Nakanishi, H. Seki, and T. Kasami: 1992, ‘The Universal Recognition Problems for Parallel Multiple Context-Free Grammars and for Their Subclasses’, IEICE E75-D(4), 499–508.
Leermakers, René: 1993, The Functional Treatment of Parsing, Kluwer, The Netherlands.
Michaelis, Jens and Marcus Kracht: 1996, Semilinearity as a syntactic invariant, Paper read at the Logical Aspects of Computational Linguistics Conference, Nancy, 23–25 September.
Manaster-Ramer, Alexis: 1987, ‘Dutch as a Formal Language’, Linguistics and Philosophy 10, 221–246.
Pollard, Carl J.: 1984, Generalized Phrase Structure Grammars, Head Grammars, and Natural Language, PhD thesis, Stanford University.
Radzinski, Daniel: 1991, ‘Chinese Number-Names, Tree Adjoining Languages, and Mild Context-Sensitivity’, Computational Linguistics 17(3), 277–299.
Rounds, William C.: 1988, ‘LFP: A Logic for Linguistic Descriptions and an Analysis of its Complexity’, Computational Linguistics 14(4), 1–9.
Seki, Hiroyuki, Takashi Matsumura, Mamoru Fujli, and Tadao Kasami: 1991, ‘On Multiple Context-Free Grammars’, Theoretical Computer Science 88, 191–229.
Vijay-Shanker, K.: 1987, A Study of Tree Adjoining Grammars, PhD thesis, Univ. of Pennsylvania.
Vijay-Shanker, K. and D. J. Weir: 1994, ‘The Equivalence of Four Extensions of Context-Free Grammar’, Math. Systems Theory 27, 511–546.
Weir, David J.: 1988, Characterizing Mildly Context-Sensitive Grammar Formalisms, PhD thesis, University of Pennsylvania.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Groenink, A.V. Mild Context-Sensitivity and Tuple-Based Generalizations of Context-Grammar. Linguistics and Philosophy 20, 607–636 (1997). https://doi.org/10.1023/A:1005376413354
Issue Date:
DOI: https://doi.org/10.1023/A:1005376413354