Naturally occurring speech contains only a limited amount of complex recursive structure, and this is reflected in the empirically documented difficulties that people experience when processing such structures. We present a connectionist model of human performance in processing recursive language structures. The model is trained on simple artificial languages. We find that the qualitative performance profile of the model matches human behavior, both on the relative difficulty of center‐embedding and cross‐dependency, and between the processing of these complex recursive structures and (...) right‐branching recursive constructions. We analyze how these differences in performance are reflected in the internal representations of the model by performing discriminant analyses on these representations both before and after training. Furthermore, we show how a network trained to process recursive structures can also generate such structures in a probabilistic fashion. This work suggests a novel explanation of people's limited recursive performance, without assuming the existence of a mentally represented competence grammar allowing unbounded recursion. (shrink)

A U-shaped curve in a cognitive-developmental trajectory refers to a three-step process: good performance followed by bad performance followed by good performance once again. U-shaped curves have been observed in a wide variety of cognitive-developmental and learning contexts. U-shaped learning seems to contradict the idea that learning is a monotonic, cumulative process and thus constitutes a challenge for competing theories of cognitive development and learning. U-shaped behavior in language learning (in particular in learning English past tense) has become a central (...) topic in the Cognitive Science debate about learning models. Antagonist models (e.g., connectionism versus nativism) are often judged on their ability of modeling or accounting for U-shaped behavior. The prior literature is mostly occupied with explaining how U-shaped behavior occurs. Instead, we are interested in the necessity of this kind of apparently inefficient strategy. We present and discuss a body of results in the abstract mathematical setting of (extensions of) Gold-style computational learning theory addressing a mathematically precise version of the following question: Are there learning tasks that require U-shaped behavior? All notions considered are learning in the limit from positive data. We present results about the necessity of U-shaped learning in classical models of learning as well as in models with bounds on the memory of the learner. The pattern emerges that, for parameterized, cognitively relevant learning criteria, beyond very few initial parameter values, U-shapes are necessary for full learning power! We discuss the possible relevance of the above results for the Cognitive Science debate about learning models as well as directions for future research. (shrink)

Embedded and embodied approaches to cognition urge that (1) complicated internal representations may be avoided by letting features of the environment drive behavior, and (2) environmental structures can play an enabling role in cognition, allowing prior cognitive processes to solve novel tasks. Such approaches are thus in a natural position to oppose the ‘thesis of linguistic structuring’: The claim that the ability to use language results in a wholesale recapitulation of linguistic structure in onboard mental representation. Prominent examples of researchers (...) adopting this critical stance include Andy Clark, Michael Wheeler, and Mark Rowlands. But is such opposition warranted? Since each of these authors advocate accounts of mental representation that are broadly connectionist, I survey research on formal language computation in artificial neural networks, and argue that results indicate a strong form of the linguistic structuring thesis is true: Internal representational systems recapitulate significant linguistic structure, even on a connectionist account of mental representation. I conclude by sketching how my conclusion can nonetheless be viewed as consistent with and complimentary to an embedded/embodied account of the role of linguistic structure in cognition. (shrink)

We introduce and study a natural extension of Marcus external contextual grammars. This mathematically simple mechanism which generates a proper subclass of simple matrix languages, known to be mildly context-sensitive ones, is still mildly context-sensitive. Furthermore, we get an infinite hierarchy of mildly context-sensitive families of languages. Then we attempt to fill a gap regarding the linguistic relevance of these mechanisms which consists in defining a tree structure on the strings generated by many-dimensional external contextual grammars, and investigate some related (...) issues. Several open problems are finally discussed. (shrink)

We give a proof-theoretic and algorithmic complexity analysis for systems introduced by Morrill to serve as the core of the CatLog categorial grammar parser. We consider two recent versions of Morrill’s calculi, and focus on their fragments including multiplicative (Lambek) connectives, additive conjunction and disjunction, brackets and bracket modalities, and the! subexponential modality. For both systems, we resolve issues connected with the cut rule and provide necessary modifications, after which we prove admissibility of cut (cut elimination theorem). We also prove (...) algorithmic undecidability for both calculi, and show that categorial grammars based on them can generate arbitrary recursively enumerable languages. (shrink)

Categorial grammar is well-known for its elegant analysis of coordination enabled by the flexible notion of constituency it entertains. However, to date, no systematic study exists that examines whether this analysis has any obvious empirical advantage over alternative analyses of nonconstituent coordination available in phrase structure-based theories of syntax. This paper attempts precisely such a comparison. We compare the direct constituent coordination analysis of non-canonical coordinations in categorial grammar with an ellipsis-based analysis of the same phenomena in the recent HPSG (...) literature. We provide a set of empirical evidence, consisting of cases in which non-canonical coordinations interact with scopal operators of various sorts, which systematically falsifies the predictions of the latter, ‘linearization-based’ ellipsis approach to coordination. We propose an alternative analysis in a variant of categorial grammar called Hybrid Type-Logical Categorial Grammar. The proposed framework builds on both the Lambek-inspired variants of categorial grammar and a more recent line of work modelling word order via a lambda calculus for the prosodic component. The flexible syntax–semantics interface of this framework straightforwardly captures the interactions between non-canonical coordinations and scopal expressions, demonstrating the broader empirical payoff of the direct constituent coordination analysis of non-canonical coordinations pioneered by Steedman :523–568, 1985; Linguist Philos 13:207–263, 1990) and Dowty hitherto not explicitly recognized in the literature. (shrink)

Some modifications are suggested to recent (1985) generalised phrase-structure grammar which make the formalism more suitable to computational use, and at the same time provide a clear and elegant redefinition for parts of the formalism which are standardly complex and ill-defined. It is shown how the feature-instantiation principles can be represented as explicit rules in a format similar to metarules, and how a grammar of four parts, immediate-dominance rules, linear-precedence rules, metarules, and these new propagation rules, can be used to (...) produce the ordinary GPSG analyses of English. Methods of computational implementation are discussed, in particular it is suggested that the parts of the grammar are most conveniently interpreted as instructions as to how to produce a set of context-free phrase-structure rules which can be used with a simple left-corner parser. (shrink)

A lengthy debate in the philosophy of the cognitive sciences has turned on whether the phenomenon known as ‘systematicity’ of language and thought shows that connectionist explanatory aspirations are misguided. We investigate the issue of just which phenomenon ‘systematicity’ is supposed to be. The much-rehearsed examples always suggest that being systematic has something to do with ways in which some parts of expressions in natural languages (and, more conjecturally, some parts of thoughts) can be substituted for others without altering well-formedness. (...) We show that under one construal this yields a grossly weak claim that is not just compatible with a narrow version of associationist psychology but essentially coincides with a formalization of its descriptive power. Under another construal we get a claim (apparently unintended) that requires natural languages to fall within the context-free class, a claim that most linguists regard as too strong. Looking more closely at this proposed reconstruction of systematicity leads us to endorse, with further illustrations, the suggestion of Johnson (2004) that systematicity as a matter of substitutability of co-categorial constituents for one another does not appearto hold of natural languages at all. The appeal of the ill-delineated notion of systematicity may lie in the fact that within certain subclasses of lexical items mutual intersubstitutability does seem to hold, and theexplanation for that lies in a limitation on human memory: we simply cannot learn separate privileges of syntactic distribution for all of the huge number of words and phrases that we know. (shrink)

We examine an argument for the non-context-freeness of English that has received virtually no discussion in the literature. It is based on adjuncts of the form 'X or no X', where X is a nominal. The construction has been held to exemplify unbounded syntactic reduplication. We argue that although the argument can be made in a mathematically valid form, its empirical basis is not secure. First, the claimed unbounded syntactic identity between nominals does not always hold in attested cases, and (...) second, an understanding of the semantics of the construction removes the necessity of making reference to any syntactic reduplication. (shrink)

We provide a semantic analysis of respective readings, including butnot limited to the interpretation of examples containing the adverbrespectively, which accounts for a number of facts that haveeither proven difficult for previous studies or heretofore goneunnoticed in the literature. The analysis introduces the new notionsof property sum and proposition sum which integrate smoothly with existing analyses of plurals and distributivity. The analysis also admits of a straightforward account of previouslyunacknowledged examples involving filler-gap dependencies that areproblematic for contemporary syntactic theories. Ramifications (...) anddirections for future research are discussed. (shrink)

This book sets out the foundations, methodology, and practice of a formal framework for the description of language. The approach embraces the trends of lexicalism and compositional semantics in computational linguistics, and theoretical linguistics more broadly, by developing categorial grammar into a powerful and extendable logic of signs. Taking Montague Grammar as its point of departure, the book explains how integration of methods from philosophy (logical semantics), computer science (type theory), linguistics (categorial grammar) and meta-mathematics (mathematical logic ) provides a (...) categorial foundation with coverage including intensionality, quantification, featural polymorphism, domains and constraints. For the first time, the book systematises categorial thinking into a unified program which is at once both logically secured, and a practical tool for pure lexical grammar development with type-theoretic semantics. It should be of interest to all those active in computational linguistics and formal grammar and is suitable for use at advanced undergraduate, postgraduate, and research levels. (shrink)

Pāṇini's fourth century BC Sanskrit grammar uses rewrite rules utilizing an explicit formal language defined through a semi-formal metalanguage. The grammar is generative, meaning that it is capable of expressing a potential infinity of well-formed Sanskrit sentences starting from a finite symbolic inventory. The grammar's operational rules involve extensive use of auxiliary markers, in the form of Sanskrit phonemes, to control grammatical derivations. Pāṇini's rules often utilize a generic context-sensitive format to identify terms used in replacement, modification or deletion operations. (...) The context-sensitive rule format is itself defined using Pāṇini's more general method of auxiliary markers, the latter used to define many dozens of linguistic categories and rules controlling derivations of Sanskrit sentences through the manipulation of ‘non-terminal’ and ‘terminal’ symbols. This technique for controlling formal derivations was rediscovered by Emil Post in the 1920s and later shown by him to be ca... (shrink)

An important topic in the evolution of language is the kinds of grammars that can be computed by humans and other animals. Fitch and Hauser () approached this question by assessing the ability of different species to learn 2 grammars, (AB)n and An Bn. An Bn was taken to indicate a phrase structure grammar, eliciting a center‐embedded pattern. (AB)n indicates a grammar whose strings entail only local relations between the categories of constituents. F&H's data suggest that humans, but not tamarin (...) monkeys, learn an An Bn grammar, whereas both learn a simpler (AB)n grammar (). In their experiments, the A constituents were syllables pronounced by a female voice, whereas the B constituents were syllables pronounced by a male voice. This study proposes that what characterizes the An Bn exemplars is the distributional regularities of the syllables pronounced by either a male or a female rather than the underlying, more abstract patterns. This article replicates F&H's data and reports new controls using either categories similar to those in F&H or less salient ones. This article shows that distributional regularities explain the data better than grammar learning. Indeed, when familiarized with An Bn exemplars, participants failed to discriminate A3 B2 and A2 B3 from An Bn items, missing the crucial feature that the number of As must equal the number of Bs. Therefore, contrary to F&H, this study concludes that no syntactic rules implementing embedded nonadjacent dependencies were learned in these experiments. The difference between human linguistic abilities and the putative precursors in monkeys deserves further exploration. (shrink)