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

Get fulltext from our e-platform
JBE logo with link
PDF logo with download linkDownload PDF
authorization required

Mixed computation

Grammar up and down the Chomsky hierarchy

 | University of Oxford
Published online: 5 November 2021
DOI logo with link
https://doi.org/10.1075/elt.00034.kri
Abstract
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.
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
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 logo with link to 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 logo with link to 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. Google Scholar logo with link to Google Scholar
Allwood, J., Andersson, L-G. & Dahl, Ö. (1977). Logic in Linguistics. Oxford: OUP. Google Scholar logo with link to Google Scholar
Bach, E. (1976). An Extension of Classical Transformational Grammar. In Problems of Linguistic Metatheory (pp. 183–224). Michigan State University.Google Scholar logo with link to Google Scholar
Borsley, R. D. (2005). Against CoordP. Lingua 1151. 461–482. Google Scholar logo with link to Google 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 logo with link to Google Scholar
(1986). Barriers. Cambridge, Mass.: MIT Press.Google Scholar logo with link to Google Scholar
(2013). Problems of Projection. Lingua 1301, 33–49. Google Scholar logo with link to Google 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 logo with link to 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 logo with link to Google Scholar
(2010). The Syntax of Adjectives. A Comparative Study. Cambridge, Mass.: MIT Press. Google Scholar logo with link to Google 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 logo with link to 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. Google Scholar logo with link to Google Scholar
(2012). Compositionality as an empirical problem. In C. Baker & P. Jacobson (eds.), Direct Compositionality (pp. 23–101). Oxford: OUP.Google Scholar logo with link to Google Scholar
Dowty, D., Wall, R. & Peters, S. (1980). Introduction to Montague semantics. Dordrecht: Reidel. Google Scholar logo with link to Google Scholar
Emonds, J. (1976). A Transformational Approach to English Syntax. New York: Academic Press.Google Scholar logo with link to Google Scholar
Epstein, R. (2011). Classical mathematical logic. Princeton: Princeton University Press. Google Scholar logo with link to Google Scholar
Frank, R. (2013). Tree adjoining grammar. In M. den Dikken (ed.) The Cambridge Handbook of Generative Syntax (pp. 226–261). Cambridge: CUP. Google Scholar logo with link to Google 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 logo with link to Google Scholar
Greibach, S. (1965). A New Normal-Form Theorem for Context-Free Phrase Structure Grammars. Journal of the ACM 12(1), 42–52. Google Scholar logo with link to Google Scholar
Jackendoff, R. (1977). X-bar syntax: A study of phrase structure. Cambridge, Mass.: MIT Press.Google Scholar logo with link to 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 logo with link to 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. Google Scholar logo with link to Google Scholar
Joshi, A. & Kulick, S. (1997). Partial Proof Trees as Building Blocks for a Categorial Grammar. Linguistics and Philosophy 20(6). 637–667. Google Scholar logo with link to Google 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. Google Scholar logo with link to Google Scholar
Kayne, R. (1984). Connectedness and Binary Branching. Dordrecht: Foris. Google Scholar logo with link to Google Scholar
(1994). The Antisymmetry of Syntax. Cambridge, Mass.: MIT Press.Google Scholar logo with link to 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 logo with link to Google Scholar
Krivochen, D. G. & L. García Fernández. (2019). On the position of subjects in Spanish periphrases. Borealis, 8(1), 1–33. Google Scholar logo with link to Google Scholar
Ladusaw, W. (1980). Polarity sensitivity as inherent scope relations. Bloomington: Indiana University Linguistics Club.Google Scholar logo with link to 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 logo with link to Google Scholar
May, R. (1985). Logical Form: Its Structure and Derivation. Cambridge, Mass.: MIT Press.Google Scholar logo with link to Google Scholar
McCawley, J. (1971). Interpretative semantics meets Frankenstein. Foundations of Language 71, 285–296.Google Scholar logo with link to Google Scholar
(1998). The Syntactic Phenomena of English. Chicago: University of Chicago Press.Google Scholar logo with link to Google Scholar
Newman, S. (1946). On the stress system of English. Word 21. 171–187. Google Scholar logo with link to Google 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 logo with link to Google Scholar
Postal, P. (1964). Constituent Structure. Bloomington, Indiana: University of Bloomington.Google Scholar logo with link to Google Scholar
(2010). Edge-Based Clausal Syntax. Cambridge, Mass.: MIT Press. Google Scholar logo with link to Google Scholar
Progovac, L. (1998). Structure for coordination. Glot International 3(7), 3–6.Google Scholar logo with link to Google Scholar
Reich, P. (1969). The finiteness of natural languages. Language 45(4), 831–843. Google Scholar logo with link to Google 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 logo with link to 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. Google Scholar logo with link to Google Scholar
(2018). Rhetorical meaning. Linguistic Frontiers 1(1). 1–8. Google Scholar logo with link to Google 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 logo with link to Google Scholar
Shieber, S. (1985). Evidence against the Context-Freeness of Natural Language. Linguistics and Philosophy 8(3), 333–343. Google Scholar logo with link to Google Scholar
Stabler, E. (1997). Derivational Minimalism. In C. Retoré (ed.), Logical Aspects of Computational Linguistics (pp. 68–95). New York: Springer. Google Scholar logo with link to Google Scholar
(2013). The epicenter of linguistic behavior. In M. Sanz, I. Laka & M. Tanenhaus, (eds.), Language Down the Garden Path. Oxford: OUP. 316–323. Google Scholar logo with link to Google 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. Google Scholar logo with link to Google 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 logo with link to Google Scholar
Uriagereka, J. (2008). Syntactic anchors: on semantic structuring. Cambridge: CUP. Google Scholar logo with link to Google Scholar
(2012). Spell-Out and the Minimalist Program. Oxford: OUP.Google Scholar logo with link to Google Scholar
XTAG group. (2001). A lexicalized TAG for English. Technical report, University of Pennsylvania. [URL]
Cited by (3)

Cited by three other publications

Krivochen, Diego Gabriel
2025. Different and Proud of It: A TAG Perspective on the Coordination of Unlike Categories. Studia Linguistica DOI logo
Padovan, Andrea
2024.  Diego Gabriel Krivochen, Syntax on the edge: A graph-theoretic analysis of sentence structure. Leiden & Boston, MA: Brill, 2023. Pp. xxi + 518.. Journal of Linguistics 60:4 ► pp. 929 ff. DOI logo
[no author supplied]
2025. Notes. In Genes, Brains, Evolution and Language, ► pp. 439 ff. DOI logo

This list is based on CrossRef data as of 8 december 2025. Please note that it may not be complete. Sources presented here have been supplied by the respective publishers. Any errors therein should be reported to them.

Mobile Menu Logo with link to supplementary files background Layer 1 prag Twitter_Logo_Blue