Cover not available
Article published In:
Formal Language Theory and its Relevance for Linguistic Analysis
Edited by Diego Gabriel Krivochen
[Evolutionary Linguistic Theory 3:2] 2021
► pp. 215–244

Mixed computation

Grammar up and down the Chomsky hierarchy

| University of Oxford
Proof-theoretic models of grammar are based on the view that an explicit characterization of a language comes in the form of the recursive enumeration of strings in that language. That recursive enumeration is carried out by a procedure which strongly generates a set of structural descriptions Σ and weakly generates a set of strings S; a grammar is thus a function that pairs an element of Σ with elements of S. Structural descriptions are obtained by means of Context-Free phrase structure rules or via recursive combinatorics and structure is assumed to be uniform: binary branching trees all the way down. In this work we will analyse natural language constructions for which such a rigid conception of phrase structure is descriptively inadequate and propose a solution for the problem of phrase structure grammars assigning too much or too little structure to natural language strings: we propose that the grammar can oscillate between levels of computational complexity in local domains, which correspond to elementary trees in a lexicalised Tree Adjoining Grammar.
Keywords: syntax, derivations, mixed computation, tree adjoining grammars, compositionality
Article outline
  • 1.Introduction
  • 2.Empirical problems
  • 3.Towards a general solution
  • 4.Iteration and coordination
    • 4.1Symmetric coordination and flat structures
  • 5.Some conclusions
  • Notes
  • References
Published online: 5 November 2021
DOI logo
https://doi.org/10.1075/elt.00034.kri
References (59)
References
Abeillé, A. (2003). A lexicalist and construction-based approach to coordinations. In S. Müller (ed.), Proceedings of the HPSG03 Conference (pp. 5–25). Stanford: CSLI.Google Scholar
Abney, S. (1987). The English noun phrase in its sentential aspect. PhD thesis, MIT.
Alexiadou, A. (2014). The syntax of adjectives. In A. Carnie, Y. Sato & D. Siddiqi. (eds.), Routledge Handbook of Syntax (pp. 89–107). London: Routledge.Google Scholar
Aljović, N. (2010). Syntactic positions of attributive adjectives. In P. Cabredo Hofherr & O. Matushansky (eds.), Adjectives: Formal analyses on syntax and semantics (pp. 29–52). Amsterdam: John Benjamins. DOI logoGoogle Scholar
Allwood, J., Andersson, L-G. & Dahl, Ö. (1977). Logic in Linguistics. Oxford: OUP. DOI logoGoogle Scholar
Bach, E. (1976). An Extension of Classical Transformational Grammar. In Problems of Linguistic Metatheory (pp. 183–224). Michigan State University.Google Scholar
Borsley, R. D. (2005). Against CoordP. Lingua 1151. 461–482. DOI logoGoogle Scholar
Bortolotto, L. (2016). The Syntax of Relational Adjectives in Romance. PhD thesis, University of Venice.
Chandlee, J. (2014). Strictly Local Phonological Processes. PhD thesis, University of Delaware.
Chomsky, N. (1965). Aspects of the Theory of Syntax. Cambridge, Mass.: MIT Press.Google Scholar
(1986). Barriers. Cambridge, Mass.: MIT Press.Google Scholar
(2013). Problems of Projection. Lingua 1301, 33–49. DOI logoGoogle Scholar
Chomsky, N. & Miller, G. (1963). Introduction to the Formal Analysis of Natural Languages. In R. Luce, R. Bush & E. Galanter (eds.), Handbook of Mathematical Psychology (pp. 269–321). New York: Wiley & Sons.Google Scholar
Cinque, G. (1994). On the Evidence for Partial N-Movement in the Romance DP. In G. Cinque, J. Koster, J.-Y. Pollock, L. Rizzi & R. Zanuttini (eds.), Paths towards Universal Grammar (pp. 85–110). Washington, D.C.: Georgetown University Press.Google Scholar
(2010). The Syntax of Adjectives. A Comparative Study. Cambridge, Mass.: MIT Press. DOI logoGoogle Scholar
De Vos, M. (2005). The syntax of pseudo-coordination in English and Afrikaans. PhD thesis, Leiden University.
Dolatian, H. & Heinz, J. (2019). Learning reduplication with 2-way finite-state transducers. Proceedings of the 14th International Conference on Grammatical Inference, 67–80.Google Scholar
Dowty, D. (2003). The Dual Analysis of Adjuncts/Complements in Categorial Grammar. In E. Lang, C. Maienborn & C. Fabricius-Hansen (eds.), Modifying Adjuncts (pp. 33–66). Berlin: de Gruyter. DOI logoGoogle Scholar
(2012). Compositionality as an empirical problem. In C. Baker & P. Jacobson (eds.), Direct Compositionality (pp. 23–101). Oxford: OUP.Google Scholar
Dowty, D., Wall, R. & Peters, S. (1980). Introduction to Montague semantics. Dordrecht: Reidel. DOI logoGoogle Scholar
Emonds, J. (1976). A Transformational Approach to English Syntax. New York: Academic Press.Google Scholar
Epstein, R. (2011). Classical mathematical logic. Princeton: Princeton University Press. DOI logoGoogle Scholar
Frank, R. (2013). Tree adjoining grammar. In M. den Dikken (ed.) The Cambridge Handbook of Generative Syntax (pp. 226–261). Cambridge: CUP. DOI logoGoogle Scholar
Fukui, N. & Narita, H. (2014). Merge, labelling, and projection. In A. Carnie, Y. Sato & D. Siddiqi (eds.) The Routledge Handbook of Syntax (pp. 3–23). London: Routledge.Google Scholar
Greibach, S. (1965). A New Normal-Form Theorem for Context-Free Phrase Structure Grammars. Journal of the ACM 12(1), 42–52. DOI logoGoogle Scholar
Jackendoff, R. (1977). X-bar syntax: A study of phrase structure. Cambridge, Mass.: MIT Press.Google Scholar
Jacobson, P. (2012). Direct Compositionality. In W. Hinzen, E. Machery & M. Werning (eds.) The Oxford Handbook of Compositionality (pp. 109–129). Oxford: OUP.Google Scholar
Joshi, A. (1985). Tree adjoining grammars. In D. Dowty, L. Karttunen & A. Zwicky (eds.) Natural Language Parsing (pp. 206–250). Cambridge, Mass.: CUP. DOI logoGoogle Scholar
Joshi, A. & Kulick, S. (1997). Partial Proof Trees as Building Blocks for a Categorial Grammar. Linguistics and Philosophy 20(6). 637–667. DOI logoGoogle Scholar
Joshi, A. & Schabes, Y. (1991). Tree-Adjoining Grammars and Lexicalized Grammars. Technical Reports (CIS). Paper 445. [URL]
Karlsson, F. (2010). Syntactic recursion and iteration. In H. van der Hulst (ed.) Recursion and Human Language (pp. 43–67). Berlin: Mouton de Gruyter. DOI logoGoogle Scholar
Kayne, R. (1984). Connectedness and Binary Branching. Dordrecht: Foris. DOI logoGoogle Scholar
(1994). The Antisymmetry of Syntax. Cambridge, Mass.: MIT Press.Google Scholar
Krivochen, D. G. (2015). On Phrase Structure building and Labeling algorithms: towards a non-uniform theory of syntactic structures. The Linguistic Review 32(3). 515–572.Google Scholar
Krivochen, D. G. & L. García Fernández. (2019). On the position of subjects in Spanish periphrases. Borealis, 8(1), 1–33. DOI logoGoogle Scholar
Ladusaw, W. (1980). Polarity sensitivity as inherent scope relations. Bloomington: Indiana University Linguistics Club.Google Scholar
Lasnik, H. (2011). What Kind of Computing Device is the Human Language Faculty? In A-M. Di Sciullo & C. Boeckx (eds.) The Biolinguistic Enterprise (pp. 354–365). Oxford: OUP.Google Scholar
May, R. (1985). Logical Form: Its Structure and Derivation. Cambridge, Mass.: MIT Press.Google Scholar
McCawley, J. (1971). Interpretative semantics meets Frankenstein. Foundations of Language 71, 285–296.Google Scholar
(1998). The Syntactic Phenomena of English. Chicago: University of Chicago Press.Google Scholar
Newman, S. (1946). On the stress system of English. Word 21. 171–187. DOI logoGoogle Scholar
Osborne, T. (2014). Dependency grammar. In A. Carnie, Y. Sato & D. Siddiqi. (eds.) Routledge Handbook of Syntax (pp. 604–626). London: Routledge.Google Scholar
Postal, P. (1964). Constituent Structure. Bloomington, Indiana: University of Bloomington.Google Scholar
(2010). Edge-Based Clausal Syntax. Cambridge, Mass.: MIT Press. DOI logoGoogle Scholar
Progovac, L. (1998). Structure for coordination. Glot International 3(7), 3–6.Google Scholar
Reich, P. (1969). The finiteness of natural languages. Language 45(4), 831–843. DOI logoGoogle Scholar
Ross, J. R. (1967). Constraints on Variables in Syntax. PhD Thesis, MIT.
Sarkar, A. & A. Joshi. (1997). Handling coordination in a tree adjoining grammar. Technical report, University of Pennsylvania.Google Scholar
Schmerling, S. (1975). Asymmetric Conjunction and rules of Conversation. In P. Cole & J. Morgan (eds.), Syntax and Semantics 3: Speech Acts, 211–231. New York: Academic Press. DOI logoGoogle Scholar
(2018). Rhetorical meaning. Linguistic Frontiers 1(1). 1–8. DOI logoGoogle Scholar
Scott, G-J. (2002). Stacked adjectival modification and the structure of nominal phrases. In G. Cinque (ed.) Functional structure in DP and IP. (pp. 91–120). Oxford: OUP.Google Scholar
Shieber, S. (1985). Evidence against the Context-Freeness of Natural Language. Linguistics and Philosophy 8(3), 333–343. DOI logoGoogle Scholar
Stabler, E. (1997). Derivational Minimalism. In C. Retoré (ed.), Logical Aspects of Computational Linguistics (pp. 68–95). New York: Springer. DOI logoGoogle Scholar
(2013). The epicenter of linguistic behavior. In M. Sanz, I. Laka & M. Tanenhaus, (eds.), Language Down the Garden Path. Oxford: OUP. 316–323. DOI logoGoogle Scholar
Steedman, M. (2019). Combinatory Categorial Grammar. In A. Kertész, E. Moravcsik & C. Rákosi (eds.), Current Approaches to Syntax: A Comparative Handbook (pp. 389–420). Berlin: de Gruyter. DOI logoGoogle Scholar
Svenonius, P. (1994). On the structural location of the attributive adjective. Proceedings of the West Coast Conference on Formal Linguistics 121, 439–454.Google Scholar
Uriagereka, J. (2008). Syntactic anchors: on semantic structuring. Cambridge: CUP. DOI logoGoogle Scholar
(2012). Spell-Out and the Minimalist Program. Oxford: OUP.Google Scholar
XTAG group. (2001). A lexicalized TAG for English. Technical report, University of Pennsylvania. [URL]